#include<bits/stdc++.h>
using namespace std;
#define y1 y114514
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(), a.end()
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef long long ll;
const int M = 998244353;

const ll inf = 1e16;

const int maxn = 1005;
pair<ll, int> d[maxn];
int n, m;
vector<pii> g[maxn];
int ans;

void solve(int s){
    for(int i = 1; i <= n; ++i)
        d[i] = mkp(inf, 0);
    d[s] = mkp(0, 0);
    queue<int> q;
    for(auto e : g[s]){
        d[e.fi] = min(d[e.fi], mkp(1LL * e.se, 0));
        q.push(e.fi);
    }
    while(!q.empty()){
        int t = q.front();
        for(auto e : g[t]){
            auto tmp = mkp(d[t].fi + e.se, max(d[t].se, t));
            if(tmp < d[e.fi]){
                d[e.fi] = tmp;
                q.push(e.fi);
            }
        }
        q.pop();
    }
    for(int i = 1; i <= n; ++i)
        ans += d[i].se;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i) vector<pii>().swap(g[i]);
        for(int i = 1; i <= m; ++i){
            static int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            g[u].pb(mkp(v, w));
            g[v].pb(mkp(u, w));
        }
        ans = 0;
        for(int i = 1; i <= n; ++i)
            solve(i);
        printf("%d\n", ans % M);
    }
    
    return 0;
}