#include<bits/stdc++.h>
#define mo 998244353
#define INF 100000000000000ll
using namespace std;
typedef long long ll;
struct edge{int go,w,next;} a[10000];
int cnt,End[10000];
inline void add(int u,int v,int w){  
  a[++cnt].go=v;a[cnt].w=w;a[cnt].next=End[u];End[u]=cnt;
}  
int S,ans,n,m,q[2000005],in[2005];
bool flag[20005];
ll f[20005],ff[20005];
bool spfa(){  
  int h=0,t=1;
  for (int i=1;i<=n;i++) f[i]=INF,flag[i]=0;  
  f[S]=0;q[1]=S;flag[S]=true;  
  while (h!=t){  
    h++;int now=q[h];  
    for (int i=End[now];i;i=a[i].next){  
      int go=a[i].go;  
      if (f[now]+a[i].w<f[go]){  
        f[go]=f[now]+a[i].w;
        if (!flag[go]) {  
          flag[go]=true;t++;q[t]=go;  
        }  
      }  
    }  
    flag[now]=false;  
  }  
  for (int i=1;i<=n;i++) in[i]=0;
  for (int now=1;now<=n;now++)
      for (int i=End[now];i;i=a[i].next) if (f[now]+a[i].w==f[a[i].go]) in[a[i].go]++;
  for (int i=1;i<=n;i++) flag[i]=0,ff[i]=INF;
  int l=1,r=1;q[1]=S;flag[S]=1;ff[S]=0;
  while (r){
      int now=q[r--];
      for (int i=End[now];i;i=a[i].next) if (f[now]+a[i].w==f[a[i].go]){
          ff[a[i].go]=min(ff[a[i].go],max(ff[now],now==S?0ll:now));
          in[a[i].go]--;
          if (in[a[i].go]==0){
              q[++r]=a[i].go;
          }
      }
  }
  for (int i=1;i<=n;i++){
      ans+=ff[i];
      ans%=mo;
  }
}  
int main(){
    int tt;scanf("%d",&tt);
    for (;tt--;){
        scanf("%d%d",&n,&m);
        cnt=0;
        for (int i=1;i<=n;i++) End[i]=0;
        for (int i=1;i<=m;i++){
            int x,y,z;scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        ans=0;
        for (S=1;S<=n;S++) spfa();
        printf("%d\n",ans);
    }
}