#include <bits/stdc++.h>

using namespace std;


#define rep(i, l, r) for(int i = l; i <= r; ++i)
#define lep(i, l, r) for(int i = l; i < r; ++i)
#define irep(i, r, l) for(int i = r; i >= l; --i)
#define ilep(i, r, l) for(int i = r; i > l; --i)

#define ge getchar()
#define Re read()

inline int read() {
    int x = 0, ch;
    while(!isdigit(ch = ge)) ;
    while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
    return x;
}

typedef long long ll;

const int MAX_N = 2007;
const int MOD = 998244353;

struct node {
    int u, mn;
    ll d;

    bool operator < (const node& rhs) const {
        return d == rhs.d ? mn > rhs.mn : d > rhs.d;
    }
};
priority_queue<node> q;

int N, M;
int head[MAX_N], to[MAX_N << 1], nxt[MAX_N << 1], cap;
int res, mn[MAX_N];
ll dis[MAX_N << 1], d[MAX_N];
bool vis[MAX_N];

inline void addEdge (int u, int v, int w) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
    dis[cap] = w;
}

inline void solve (int s) {
    rep (i, 1, N) d[i] = 1e15, mn[i] = N + 1, vis[i] = false;
    d[s] = 0, mn[s] = 0;
    q.push((node){s, 0, 0});
    while (!q.empty()) {
        node t = q.top(); q.pop();
        int x = t.u;
        if (vis[x]) continue;
        vis[x] = true;
        for (int i = head[x]; i; i = nxt[i])
            if (d[to[i]] > d[x] + dis[i]) {
                d[to[i]] = d[x] + dis[i];
                mn[to[i]] = max(mn[x], x != s ? x : 0);
                q.push((node){to[i], mn[to[i]], d[to[i]]}); 
            } else if (d[to[i]] == d[x] + dis[i] && max(mn[x], x != s ? x : 0) < mn[to[i]]) {
                mn[to[i]] = max(mn[x], x);
                q.push((node){to[i], mn[to[i]], d[to[i]]});
            }
    }
    // printf("%d:\n", s);
    // rep (i, 1, N) printf("%d ", mn[i]); puts("");
    rep (i, 1, N) if (i != s) res = (res + mn[i]) % MOD;
}

int main () {
    int T = Re;
    while (T--) {
        res = 0;
        N = Re, M = Re;
        memset(head, 0, (N + 1) << 2);
        cap = 0;
        int u, v, w;
        rep (i, 1, M) {
            u = Re, v = Re, w = Re;
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        rep (i, 1, N) solve(i);
        printf("%d\n", res);
    }
    return 0;
}