#include <bits/stdc++.h>
using namespace std;
int n, m, ind[1005], f[1005];
vector<pair<int, int> > G[1005];
vector<int> H[1005];
long long dist[1005];
inline int solve(int s) {
    for (int i = 1; i <= n; i++) dist[i] = 1ll << 60, H[i].clear(), ind[i] = 0, f[i] = 1 << 30;
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > que;
    dist[s] = 0;
    que.push(make_pair(dist[s], s));
    while (!que.empty()) {
        int u = que.top().second;
        long long tmp = que.top().first;
        que.pop();
        if (dist[u] != tmp) continue;
        for (pair<int, int> P : G[u]) {
            int v = P.first, w = P.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                que.push(make_pair(dist[v], v));
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (pair<int, int> P : G[i]) {
            int j = P.first;
            if (dist[j] == dist[i] + P.second) {
                H[i].push_back(j);
                ind[j]++;
            }
        }
    }
    queue<int> q;
    q.push(s);
    f[s] = 0;
    int sum = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        sum += f[u];
        int tmp = (u == s ? 0 : max(u, f[u]));
        for (int v : H[u]) {
            ind[v]--;
            f[v] = min(f[v], tmp);
            if (!ind[v]) q.push(v);
        }
    }
    return sum;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) G[i].clear();
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            G[u].push_back(make_pair(v, w));
            G[v].push_back(make_pair(u, w));
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += solve(i);
        }
        printf("%d\n", ans % 998244353);
    }
    return 0;
}