#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int T,ans;
int n,m,u,v,w;
int fir[2005],nxt[4005],to[4005],len[4005],cnt;
long long d[1005];
int ma[1005],line[1005];
struct cmp{
    bool operator()(int u,int v){
        return d[u]>d[v];
    }
};

void dijkstra(int x){
    priority_queue<int,vector<int>,cmp> Q;
    for(int i=1;i<=n;i++) d[i]=1e18,ma[i]=n+1;
    d[x]=0,ma[x]=0;
    Q.push(x);
    line[x]=1;
    while(!Q.empty()){
        int v=Q.top();
        Q.pop();Q.push(v);
        v=Q.top();Q.pop();
        for(int i=fir[v];i;i=nxt[i]){
            if(d[to[i]]>d[v]+1ll*len[i]){
                d[to[i]]=d[v]+1ll*len[i];
                if(v!=x) ma[to[i]]=max(v,ma[v]);
                else ma[to[i]]=0;
                if(line[to[i]]==0){
                    Q.push(to[i]);
                    line[to[i]]=1;
                }
            }
            else if(d[to[i]]==d[v]+1ll*len[i]){
                if(v==x) ma[to[i]]=0;
                else{
                    if(ma[to[i]]>max(ma[v],v)){
                        ma[to[i]]=max(ma[v],v);
                        if(line[to[i]]==0){
                            Q.push(to[i]);
                            line[to[i]]=1;
                        }
                    }
                }
            }
        }
        line[v]=0;
    }
    for(int i=1;i<=n;i++) ans+=ma[i],ans%=mod;
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);
        cnt=0;
        memset(fir,0,sizeof(fir));
        for(int i=1;i<=m;i++){
            scanf("%d %d %d",&u,&v,&w);
            to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,len[cnt]=w;
            to[++cnt]=u,nxt[cnt]=fir[v],fir[v]=cnt,len[cnt]=w;
        }
        ans=0;
        for(int i=1;i<=n;i++) dijkstra(i);
        printf("%d\n",ans);
    }

    return 0;
}