#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;

typedef long long ll;

const ll Inf=1e18;
ll A[1005][1005];
int ans[1005][1005];
int N,M;
void Floyd_4(){
  for(int k = 1; k <= N; k++){
    for(int i = 1; i <= N; i++){
      if(k != i){
        ll t = (k<i) ? A[i][k] : A[k][i];
        if(t == Inf)  continue;
        for(int j = 1; j <= ((k<i)?k:i); j++){
          if(t+A[k][j] < A[i][j])  {
            A[i][j] = t + A[k][j];
            ans[i][j]=k;
          }
        }
        for(int j = k+1; j <= i; j++){
          if(t+A[j][k] < A[i][j])  {
            ans[i][j]=k;
            A[i][j] = t + A[j][k];
          }
        }
      }
    }
  }
  return ;
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++){
        if(i==j) A[i][j]=0;
        else A[i][j]=Inf;
        ans[i][j]=0;
      }
    }
    for(int i=0;i<M;i++){
      int x,y;
      ll va;
      scanf("%d%d%lld",&x,&y,&va);
      if(va<A[x][y]){
        A[x][y]=va;
        A[y][x]=va;
      }
    }
    Floyd_4();
    ll tmp=0;
    for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++){
        //printf("%d ",ans[i][j]);
        tmp+=ans[i][j];
        tmp%=mod;
      }
      //printf("\n");
    }
    tmp*=2;
    tmp%=mod;
    printf("%lld\n",tmp);
  }
  return 0;
}