#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int N=5005;
struct map{
    int x,y,w;
}a[N];
int T,n,m,x,y,w,k,fir[N],ne[N],ans,d[N];
long long f[N];
bool o[N];
queue <int> q;
//struct data{
//    int x;
//    //Node(int a = 0, int b = 0):x(a), y(b){};
//    bool operator<(const data &a, const data &b)
//    {
//        if (f[a.x]!=f[b.x]) return f[a.x]<f[b.x];
//        return d[a.x]<d[b.x]; 
//    }
//};

void add(int x,int y,int w)
{
    k++; a[k].x=x; a[k].y=y; a[k].w=w; ne[k]=fir[x]; fir[x]=k;
}

void work(int s)
{
    memset(f,10,sizeof(f)); f[s]=0;
//    cerr<<f[0]<<endl;
    memset(d,10,sizeof(d)); d[s]=0;
    memset(o,0,sizeof(o));// o[s]=1;
//    P.x=s;// P.d=P.f=0;
    q.push(s);
//    cerr<<s<<endl;
    while (!q.empty())
    {
        x=q.front(); q.pop();
        o[x]=0;// ans+=d[x];
        w=d[x];
        if (x!=s) w=max(w,x);
        for (int i=fir[x];i;i=ne[i])// if (!o[y=a[i].y])
        {
            y=a[i].y;
            if (f[y]>f[x]+a[i].w||(f[y]==f[x]+a[i].w&&d[y]>w))
            {
                f[y]=f[x]+a[i].w; d[y]=w;
                if (!o[y])
                {
                    o[y]=1; q.push(y);
                }
            }
        }
    }
    for (int i=1;i<=n;i++) if (f[i]!=f[0]) ans+=d[i];
}

int main()
{
    #ifdef WXY_Z
        freopen("1.in","r",stdin); 
    #endif
    cin>>T;
    while (T--)
    {
        k=ans=0; memset(fir,0,sizeof(fir));
        cin>>n>>m;
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            add(x,y,w); add(y,x,w);
        }
        for (int i=1;i<=n;i++) work(i);
        cout<<ans%998244353<<endl;
    }
}