#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=2005,MOD=998244353;
struct Graph{
    struct Edge{ int to,nxt,key; }edge[MAX_N*2];
    int head[MAX_N],top;
    void clear(int n){ memset(head,-1,sizeof(head)),top=-1; }
    inline void add(int x,int y,int k){
        edge[++top]=(Edge){y,head[x],k};
        head[x]=top;
    }
}G,G1;
ll dis[MAX_N];
int f[MAX_N],n,rd[MAX_N],ans;
priority_queue<pair<ll,int>,vector<pair<ll,int> >
    ,greater<pair<ll,int> > > q;
void dij(int x){
    memset(dis,0x3f,sizeof(ll)*(n+1));
    dis[x]=0; q.push(make_pair(dis[x],x));
    while(!q.empty()){
        int x=q.top().second; q.pop();
        for(int j=G.head[x];~j;j=G.edge[j].nxt){
            int y=G.edge[j].to;
            if(dis[x]+G.edge[j].key<dis[y]){
                dis[y]=dis[x]+G.edge[j].key;
                q.push(make_pair(dis[y],y));
            }
        }
        while(!q.empty()&&q.top().first!=dis[q.top().second]) q.pop();
    }
}
void solve(int x){
    int tx=x;
//    for(int i=1;i<=n;++i) printf("(%d)",dis[i]); puts("");
    static int q[MAX_N],left,right;
    left=1,right=0;
    memset(rd,0,sizeof(int)*(n+1));
    memset(f,0x3f,sizeof(int)*(n+1));
    G1.clear(n); f[x]=0;
    for(int i=1;i<=n;++i)
        for(int j=G.head[i];~j;j=G.edge[j].nxt){
            int y=G.edge[j].to;
            if(dis[i]+G.edge[j].key==dis[y]){
                G1.add(i,y,G.edge[j].key);
//                printf("<%d %d>",i,y);
                ++rd[y];
            }
        }
    for(int i=1;i<=n;++i)
        if(rd[i]==0) q[++right]=i;
    while(left<=right){
        int x=q[left++]; 
        for(int j=G1.head[x];~j;j=G1.edge[j].nxt){
            int y=G1.edge[j].to;
            if(x==tx) f[y]=min(f[y],0);
            else f[y]=min(f[y],max(f[x],x));
            --rd[y];
            if(rd[y]==0) q[++right]=y;
        }
    }
//    for(int i=1;i<=n;++i) printf("[%d]",f[i]);
    for(int i=1;i<=n;++i) ans=(ans+f[i])%MOD;
}
int main(){
    int T; scanf("%d",&T);
    while(T--){
        int m; scanf("%d%d",&n,&m);
        G.clear(n); ans=0;
        for(int i=1;i<=m;++i){
            int x,y,k; scanf("%d%d%d",&x,&y,&k);
            G.add(x,y,k); G.add(y,x,k);
        }
        for(int i=1;i<=n;++i){
            dij(i);
            solve(i);
        }
        printf("%d\n",ans);
    }
    return 0;
}