#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MAXN=1e3+10;
const LL INF=1e15+7;
const int mod=998244353;

int n,m; 
LL x[100][100],y[100][100],z[100][100],tans;
vector< pair<int,LL> > edge[MAXN];

int vis[MAXN],mx[MAXN];
LL dis[MAXN];
queue<int> q;

void SPFA(int s,int lim){
    for(int i=1;i<=n;i++){
        vis[i]=0;
        mx[i]=n+1;
        dis[i]=INF;
    }
    dis[s]=0; mx[s]=0; q.push(s);    
    while(!q.empty()){
        int u=q.front(); q.pop();  vis[u]=0;
        for(int i=0;i<edge[u].size();i++){
            int v=edge[u][i].first;
            LL d=edge[u][i].second;
            if (dis[v]>dis[u]+d){
                dis[v]=dis[u]+d;
                if (u==s) mx[v]=0;
                else mx[v]=max(mx[u],u);
                if (vis[v]==0){
                    vis[v]=1;
                    q.push(v);
                }
            } else if (dis[v]==dis[u]+d){
                int nv=0;
                if (u==s) nv=0;
                else nv=max(mx[u],u);
                if (nv<mx[v]){
                    mx[v]=nv;
                    if (vis[v]==0){
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        } 
    }
}

void check1(LL lim){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            y[i][j]=INF;
            if (i==j) y[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<edge[i].size();j++){
            y[i][edge[i][j].first]=min(y[i][edge[i][j].first],edge[i][j].second);
        }
    }
    for(int i=1;i<=n;i++){y[i][i]=0;
    }
    for(int k=1;k<=lim;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if (y[i][j]>y[i][k]+y[k][j]){
                    y[i][j]=y[i][k]+y[k][j];
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if (x[i][j]==y[i][j]){
                z[i][j]=min(z[i][j],lim);
            }
}

void check(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            x[i][j]=INF;
            if (i==j) x[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<edge[i].size();j++){
            x[i][edge[i][j].first]=min(x[i][edge[i][j].first],edge[i][j].second);
        }
    }
    for(int i=1;i<=n;i++){x[i][i]=0;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if (x[i][j]>x[i][k]+x[k][j]){
                    x[i][j]=x[i][k]+x[k][j];
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            z[i][j]=n;
    for(int i=0;i<=n;i++){
        check1(i);
    }
    tans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            tans+=z[i][j];
        }
}

int main(){
    default_random_engine dre(time(0));
    uniform_int_distribution<int> uidd(1,10);
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        uniform_int_distribution<> uid(1,n);
        for(int i=1;i<=n;i++) edge[i].clear();
        
        for(int i=1;i<=m;i++){
            int a,b; LL c;
            //a=uid(dre);
            //b=uid(dre);
            //c=uidd(dre);
            //cout<<a<<' '<<b<<' '<<c<<endl;
            scanf("%d%d%lld",&a,&b,&c);
            edge[a].push_back(make_pair(b,c));
            edge[b].push_back(make_pair(a,c));
        }


        //check();
        //cout<<tans<<endl;

        LL ans=0;
        for(int i=1;i<=n;i++){
            SPFA(i,n);
            for(int j=1;j<=n;j++){
                int nv=mx[j];
                if (mx[j]==n+1 || mx[j]==0) nv=0;
                ans+=nv;
                //assert(nv==z[i][j]);
                /*if (z[i][j]!=nv){
                    cout<<i<<' '<<j<<' '<<z[i][j]<<' '<<nv<<endl;
                }*/
            }
        }
        ans%=mod;
        printf("%lld\n",ans);
    }
    return 0;
}

/*
7 3 10
3 5 4
2 3 10
3 7 4
2 7 2
1 2 9
5 7 10
6 3 3
7 1 8
1 5 7
1 1 7
1 5 6
4 4 9
6 3 6
3 3 8
7 2 1
7 1 5
6 5 2
6 2 8
2 6 9

7 10
2 1 7
6 2 6
4 4 2
7 5 7
4 2 2
6 2 6
2 5 7
2 6 7
4 7 8
5 4 4
*/