#include #include #include #include #include using namespace std; #define DEBUG 0 #define MAXN 1011 typedef long long LL; const int p = 998244353; template void AddMod(T& x, int p) { if (x >= p) x -= p; } struct GRAPH { vector > > s; void ClearEdges() { for (auto& i : s) i.resize(0); } void Init(int n) { ClearEdges(); s.resize(n+1); } void AddUndi(int u, int v, int w) { s[u].emplace_back(v, w); s[v].emplace_back(u, w); } }; template void dijkstra(const GRAPH& g, int s, T dist[]) { priority_queue >q; fill(dist, dist + g.s.size(), numeric_limits::max()); dist[s] = 0; q.push(make_pair(0, s)); while (!q.empty()) { s = q.top().second; T c = -q.top().first; q.pop(); if (c > dist[s]) continue;//old version for (auto i : g.s[s]) { int v = i.first; c = i.second; if (dist[v] > dist[s] + c) { dist[v] = dist[s] + c; q.push(make_pair(-dist[v], v)); } } } } int d[MAXN]; LL dist[MAXN]; const int INF = 0x3f3f3f3f; int dfs(const GRAPH& g, int s, int t) { if (INF != d[s]) { return d[s]; } for (auto e : g.s[s]) { auto& v = e.first, w = e.second; if (dist[v] + w == dist[s]) { if (v == t) { d[s] = 0; break; } else { d[s] = min(d[s], max(v, dfs(g, v, t))); } } } if (d[s] == INF) d[s] = 0; return d[s]; } int main() { int T; GRAPH g; scanf("%d", &T); while (T--) { int n, m; scanf("%d%d", &n, &m); g.Init(n); while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); g.AddUndi(u, v, w); } int ans = 0; for (int i = 1; i <= n; ++i) { dijkstra(g, i, dist); memset(d, 0x3f, (n + 1) * sizeof(d[0])); for (int j = 1; j <= n; ++j) { AddMod(ans += dfs(g, j, i), p); } #if DEBUG for (int j = 1; j <= n; ++j) { printf("%d ", d[j]); } putchar('\n'); #endif } printf("%d\n", ans); } return 0; }