#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <utility>
#include <algorithm>

using namespace std;

const int ME = 4010;
const int MAXN = 2010;

int n, M;
int to[ME],nxt[ME],len[ME],fir[MAXN],cnt;
int dv[MAXN],zd[MAXN],iq[MAXN];
long long dis[MAXN];

int qq[MAXN],qf,qr;

void aee(int a,int b,int v){ ++cnt;to[cnt]=b;len[cnt]=v;nxt[cnt]=fir[a];fir[a]=cnt; }

const int ANS_MOD = 998244353;
long long ans;

void spfa(int st){
    dis[st]=0; zd[st]=0; dv[st]=st;
    qf=qr=0; qq[qr++]=st; iq[st]=1;
    while(qf!=qr) {
        int x = qq[qf++]; if(qf==MAXN) qf=0; iq[x]=0;
        for(int ii = fir[x];ii;ii=nxt[ii]){
            int y = to[ii];
            long long xlen = dis[x]+len[ii];
            int xll = x==st?0:max(zd[x],x);
            if(dv[y]!=st || xlen<dis[y] || (xlen==dis[y] && xll<zd[y])){
                dis[y]=xlen;
                zd[y]=xll; dv[y]=st;
                if(!iq[y]){ iq[y]=1; qq[qr++]=y; if(qr==MAXN) qr=0; }
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(dv[i]!=st)__builtin_trap();
        ans+=zd[i];
    }
    ans%=ANS_MOD;
}

void dit() {
    scanf("%d%d",&n,&M);
    cnt = 0; ans=0;
    for(int i=1;i<=n;++i)fir[i]=0,dv[i]=0;
    for(int i=0;i<M;++i){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        aee(a,b,c);
        aee(b,a,c);
    }
    for(int i=1;i<=n;++i)spfa(i);
    printf("%d\n",(int)ans);
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--)dit();
    return 0;
}