#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define clr(x,y) memset(x,y,sizeof(x))
#define in(a) a=read()
#define out(a) printf("%d\n",a)
inline ll read(){
    char c=getchar();ll f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return x*f;
}
#define mod 998244353
void MOD(int &x){if(x>=mod)x-=mod;}
#define maxn 100010
#define inf (1<<30)
int l,nxt[maxn],head[maxn],to[maxn],v[maxn]; 
void add(int x,int y,int z){l++;nxt[l]=head[x];head[x]=l;to[l]=y;v[l]=z;}
ll d[maxn];
int mx[maxn];
int bfs[maxn],u[maxn];
void dij(int X){
    int l=1,r=2;
    mx[X]=0;d[X]=0;bfs[l]=X;
    while(l<r){
        int x=bfs[l++];u[x]=0;
        FORL(i,x){
            int c=to[i];
            if(d[x]+v[i]<d[c]||(d[x]+v[i]==d[c]&&(x==X||max(mx[x],x)<mx[c]))){
                d[c]=d[x]+v[i];
                if(x!=X)mx[c]=max(mx[x],x);
                if(!u[c])bfs[r++]=c,u[c]=1;
            }
        }
    }
}
int main(){
    int t;
    in(t);
    while(t--){
        l=0;clr(head,0); 
        int n,m;
        in(n);in(m);
        FOR(i,1,m){
            int x,y,z;
            in(x);in(y);in(z);
            add(x,y,z);
            add(y,x,z);
        }
        int ans=0;
        FOR(i,1,n){
            FOR(j,1,n)d[j]=1e13,mx[j]=0;
            dij(i);
            FOR(j,1,n)MOD(ans+=mx[j]);
        }
        out(ans);
    }
}