#include <bits/stdc++.h>
#define MOD 998244353
#define inf 0x3f3f3f3f3f3f3f3fLL

using namespace std;

typedef long long ll;

struct Edge {
  int t,v,next;
  Edge() {}
  Edge(int a,int b,int c):t(a),v(b),next(c) {}
};

Edge e[4005];
int head[1005];

struct Data {
  ll d;
  int v,id;
  Data() {}
  Data(ll a,int b,int c):d(a),v(b),id(c) {}
  bool operator < (const Data & b) const {
      if (d!=b.d) return d<b.d;
      if (v!=b.v) return v<b.v;
      return id<b.id;
  }
  bool operator > (const Data & b) const {
      if (d!=b.d) return d>b.d;
      if (v!=b.v) return v>b.v;
      return id>b.id;
  }
};

Data dis[1005];
priority_queue <Data,vector<Data>,greater<Data> > q;

int dijkstra(int s,int n) {
  while (!q.empty()) q.pop();
  for(int i=1;i<=n;i++) dis[i]=Data(inf,0,i);
  dis[s]=Data(0,0,s);q.push(dis[s]);
  while (!q.empty()) {
      Data t=q.top();q.pop();
      if (dis[t.id]<t) continue;
      int x=t.id;
      for(int i=head[x];i;i=e[i].next) {
          int u=e[i].t;
          Data v(t.d+e[i].v,max(t.v,((x!=s)?x:0)),u);
          if (v<dis[u]) {
              dis[u]=v;
              q.push(dis[u]);
          }
      }
  }
  int ans=0;
  for(int i=1;i<=n;i++) ans+=dis[i].v;
  return ans;
}

int main() {
  int cases;
  scanf("%d",&cases);
  for(;cases;cases--) {
      memset(head,0,sizeof(head));
      int n,m;
      scanf("%d%d",&n,&m);
      for(int i=1;i<=m;i++) {
          int x,y,z;
          scanf("%d%d%d",&x,&y,&z);
          e[2*i-1]=Edge(y,z,head[x]);
          head[x]=2*i-1;
          e[2*i]=Edge(x,z,head[y]);
          head[y]=2*i;
      }
    int ans=0;
    for(int i=1;i<=n;i++)
      ans+=dijkstra(i,n);
    printf("%d\n",ans%MOD);
  }
  return 0;
}