#include<bits/stdc++.h>
#define ll long long
#define N 1006
#define P 998244353
using namespace std;
int n,m,pos[N],g[N][N];
ll f[N],ans;
struct data{
    int to;
    long long v;
};
vector<data>a[N];
struct Heap{
    data a[N*10];
    int sz;
    Heap(){sz=0;}
    void push(data x){
        a[++sz]=x;
        int now=sz;
        while(now!=1){
            if(x.v<a[now/2].v){
                a[now]=a[now/2];
                now/=2;
            }else break;
        }a[now]=x;
    }
    void pop(){
        a[1]=a[sz];
        sz--;
        data x=a[1];
        int now=1;
        while(1){
            if(now*2>sz)break;
            int w=now<<1;
            if(w+1<=sz&&a[w+1].v<a[w].v)++w;
            if(a[w].v<a[sz+1].v){
                a[now]=a[w];
                now=w;
            }else break;
        }
        a[now]=x;
    }
}Q;
bool b[N];
void Dij(int st){
    for(int i=1;i<=n;i++)f[i]=1e16,pos[i]=0;
    f[st]=0;
    Q.push((data){st,0});
    while(Q.sz){
        data now=Q.a[1];Q.pop();
        int x=now.to;
        for(int i=0;i<(int)a[x].size();i++){
            int y=a[x][i].to,v=a[x][i].v;
            if(f[y]>f[x]+v){
                f[y]=f[x]+v;
                if(x==st)pos[y]=0; 
                else pos[y]=max(x,pos[x]);
                Q.push((data){y,f[y]});
            }
            else if(f[y]==f[x]+v){
                pos[y]=min(pos[y],max(x,pos[x]));
                Q.push((data){y,f[y]});
            }
        }
    }
    for(int i=1;i<=n;i++)ans+=pos[i];ans%=P;
}
signed main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)a[i].clear();
        for(int i=1;i<=m;i++){
            int x,y,v;
            scanf("%d%d%d",&x,&y,&v);
            a[x].push_back((data){y,v});
            a[y].push_back((data){x,v});
        }
        ans=0;
        for(int i=1;i<=n;i++)Dij(i);
        printf("%lld\n",ans);
    }
    return 0;
}