#include #include #include #include #include #include using namespace std; struct Edge { int u, w; }; vector e[1010]; queue q; int T, n, m, u, v, w, ans, p[1010]; long long d[1010]; bool vis[1010]; int main() { scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); ans = 0; for (int i = 1; i <= n; ++i) e[i].clear(); while (m--) { scanf("%d%d%d", &u, &v, &w); e[u].push_back({v, w}); e[v].push_back({u, w}); } for (int i = 1; i <= n; ++i) { memset(vis, 0, sizeof(vis)); for (int j = 1; j <= n; ++j) { d[j] = 1e15; p[j] = n; } int l = e[i].size(); for (int j = 0; j < l; ++j) { d[e[i][j].u] = e[i][j].w; p[e[i][j].u] = 0; } d[i] = p[i] = 0; q = queue(); q.push(i); vis[i] = 1; while (!q.empty()) { int now = q.front(); q.pop(); vis[now] = 0; int l = e[now].size(); for (int j = 0; j < l; ++j) if (d[e[now][j].u] > e[now][j].w + d[now]) { d[e[now][j].u] = e[now][j].w + d[now]; p[e[now][j].u] = max(p[now], now == i ? 0 : now); if (!vis[e[now][j].u]) { q.push(e[now][j].u); vis[e[now][j].u] = 1; } } else if (d[e[now][j].u] == e[now][j].w + d[now]) { p[e[now][j].u] = min(p[e[now][j].u], max(p[now], now == i ? 0 : now)); if (!vis[e[now][j].u]) { q.push(e[now][j].u); vis[e[now][j].u] = 1; } } } for (int j = 1; j <= n; ++j) ans = (ans + p[j]) % 998244353; } printf("%d\n", ans); } return 0; }