#include <bits/stdc++.h>
using namespace std;
const int N = 1005 , mod = 998244353;
struct node{int to,next,val;}e[N<<2];
int n,m,cnt,head[N],vis[N],f[N],ans;long long dis[N];
priority_queue<pair<long long ,int > >q;
void add(int x,int y,int z){e[cnt]=(node){y,head[x],z};head[x]=cnt++;}
void Dijkstra(int S)
{
    q.push(make_pair(0,S));memset(dis,0x3f,sizeof(long long)*(n+1));
    memset(vis,0,sizeof(int)*(n+1));memset(f,0x3f,sizeof(int)*(n+1));f[S]=dis[S]=0;
    while(!q.empty())
    {
        int x=q.top().second;q.pop();if(vis[x])continue;vis[x]=1;
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to1=e[i].to;
            if(dis[x]==dis[to1]+e[i].val)
                f[x]=min(f[x],max(f[to1],(to1==S?0:to1)));
        }
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to1=e[i].to;
            if(dis[to1]>dis[x]+e[i].val)
                dis[to1]=dis[x]+e[i].val,q.push(make_pair(-dis[to1],to1));
        }
    }
    for(int i=1;i<=n;i++)(ans+=f[i])%=mod;
}
void solve()
{
    scanf("%d%d",&n,&m);memset(head,-1,sizeof(int)*(n+1));ans=cnt=0;
    for(int i=1,x,y,z;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++)Dijkstra(i);printf("%d\n",ans);
}
int main()
{
    int T; scanf("%d",&T);
    while(T--) solve();
}