#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

namespace IO {
    template <typename _T>
    inline bool read (_T& x) {
        x = 0;
        _T y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-') y = -1;
            c = getchar();
        }
        if (c == EOF) return false;
        while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
        x *= y;
        return true;
    }

    template <typename _T>
    inline _T input () {
        _T x = 0, y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-') y = -1;
            c = getchar();
        }
        if (c == EOF) return 0;
        while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
        x *= y;
        return x;
    }
};
using namespace IO;

#define reg register
#define MAX_N 2007
#define MOD 998244353
#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)
typedef long long ll;

struct node {
    int u, mn;
    ll d;

    bool operator < (const node& rhs) const {
        return d == rhs.d ? mn > rhs.mn : d > rhs.d;
    }
};
std::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]] = std::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] && std::max(mn[x], x != s ? x : 0) < mn[to[i]]) {
                mn[to[i]] = std::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 () {
#ifndef ONLINE_JUDGE
    // freopen ("in", "r", stdin);
#endif
    int T = input<int>();
    while (T--) {
        res = 0;
        read(N), read(M);
        memset(head, 0, N + 1 << 2);
        cap = 0;
        int u, v, w;
        rep (i, 1, M) {
            read(u), read(v), read(w);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        rep (i, 1, N) solve(i);
        printf("%d\n", res);
    }
    return 0;
}