#include<bits/stdc++.h>
using namespace std;
#define N 1005
int E,t,n,m,x,y,z,ans,vis[N],head[N],d2[N];
struct ji{
    int id;
    long long len;
    bool operator < (const ji &a)const{
        return (len<a.len)||(len==a.len)&&(id<a.id);
    }
}d[N];
struct ji3{
    int k;
    ji t;
    bool operator < (const ji3 &a)const{
        return a.t<t;
    }
};
priority_queue<ji3>q;
struct ji2{
    int nex,to,len;
}edge[N<<2];
void add(int x,int y,int z){
    edge[E].nex=head[x];
    edge[E].to=y;
    edge[E].len=z;
    head[x]=E++;
}
void dij(int k){
    for(int i=1;i<=n;i++)d[i]=ji{0,2000000000LL*n};
    for(int i=1;i<=n;i++)vis[i]=0;
    d[k]=ji{0,0};
    vis[k]=1;
    for(int i=head[k];i!=-1;i=edge[i].nex){
        if (ji{0,edge[i].len}<d[edge[i].to])d[edge[i].to]=ji{0,edge[i].len};
        q.push(ji3{edge[i].to,d[edge[i].to]});
    }
    d2[k]=0;
    while (!q.empty()){
        k=q.top().k;
        q.pop();
        if (vis[k])continue;
        vis[k]=1;
        ans+=d[k].id;
        d[k].id=max(d[k].id,k);
        for(int i=head[k];i!=-1;i=edge[i].nex){
            int v=edge[i].to;
            if (!vis[v]){
                d[k].len+=edge[i].len;
                if (d[k]<d[v]){
                    d[v]=d[k];
                    q.push(ji3{v,d[v]});
                }
                d[k].len-=edge[i].len;
            }
        }
    }
}
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&m);
        E=ans=0;
        for(int i=1;i<=n;i++)head[i]=-1;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        for(int i=1;i<=n;i++)dij(i);
        printf("%d\n",ans%998244353);
    }
}