#include <cstdio> #include <map> #include <queue> #include <tuple> #include <utility> #include <vector> using namespace std; using i64 = long long; constexpr int INF = 0x3f3f3f3f, START = 1, MOD = 1e9 + 7, INV_2 = 500000004; map<int, vector<pair<int, int>>> graph; vector<vector<int>> edges; vector<int> dist, cnt; void get_dist(int n, int start = START) { priority_queue<pair<int, int>> nodes; vector<bool> vis(n + 1); dist.resize(n + 1, INF); cnt.resize(n + 1, 0); cnt[start] = 1; nodes.emplace(dist[start] = 0, start); while (!nodes.empty()) { int u = nodes.top().second; nodes.pop(); if (vis[u]) continue; vis[u] = true; for (const auto nxt : graph[u]) { int v = nxt.first, w = nxt.second; if (dist[v] < dist[u] + w) continue; if (dist[v] > dist[u] + w) cnt[v] = cnt[u]; else cnt[v] += cnt[u]; dist[v] = dist[u] + w; nodes.emplace(-dist[v], v); } } } void get_edge(int n, int start = START) { queue<tuple<int, int, int>> nodes; nodes.emplace(0, 0, start); edges.resize(n + 1); while (!nodes.empty()) { auto curr = nodes.front(); int dis = get<0>(curr), step = get<1>(curr), u = get<2>(curr); nodes.pop(); if (dis > dist[u]) continue; edges[u].emplace_back(step); for (const auto& nxt : graph[u]) { int v = nxt.first, w = nxt.second; nodes.emplace(dis + w, step + 1, v); } } } inline int mod_mul(int x, int y) { return (i64)x * y % MOD; } inline int add(int x, int y) { return (x + y) % MOD; } inline int div_2(int x) { return mod_mul(x, INV_2); } int main() { // freopen("bob.in", "r", stdin); // freopen("bob.out", "w", stdout); int n, m; bool is_sub2 = true; scanf("%d %d", &n, &m); for (int i = 0; i < m; ++i) { int u, v, w; scanf("%d %d %d", &u, &v, &w); graph[u].emplace_back(v, w); if (w != 1) is_sub2 = false; } int ans = 0; get_dist(n); if (is_sub2) { for (int i = 2; i <= n; ++i) ans = add(ans, div_2(mod_mul(mod_mul(dist[i], dist[i]), mod_mul(cnt[i], cnt[i] - 1)))); } else { get_edge(n); for (int i = 2; i <= n; ++i) { int len = cnt[i]; for (int j = 0; j < len; ++j) { for (int k = j + 1; k < len; ++k) ans = add(ans, mod_mul(edges[i][j], edges[i][k])); } } } printf("%d\n", ans); return 0; }