#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 2333333333333333333LL
#define pll pair<ll,ll>

struct node { int t,next;ll v; }a[4010];

priority_queue<pll,vector<pll>,greater<pll> > q;

ll dis[2010],ans;
int head[2010],mx[2010],t,n,m,tot;

inline int rd()
{
    int x=0;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar());
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

inline void add(int x,int y,int z)
{
    a[++tot].t=y;a[tot].v=z;a[tot].next=head[x];head[x]=tot;
}

inline void work(int vs)
{
    for (int i=1;i<=n;i++) dis[i]=inf;
    for (int i=1;i<=n;i++) mx[i]=n+1;
    dis[vs]=0;mx[vs]=0;
    while (!q.empty()) q.pop();
    q.push(pll(0,vs));
    while (!q.empty())
    {
        pll hh=q.top();q.pop();
        int x=hh.second;
        if (dis[x]<hh.first) continue;
        for (int i=head[x];i;i=a[i].next)
        {
            int t=a[i].t;
            if (dis[t]>dis[x]+a[i].v)
            {
                dis[t]=dis[x]+a[i].v;
                if (x!=vs) mx[t]=max(mx[x],x);
                else mx[t]=0;
                q.push(pll(dis[t],t));
            }
            else if (dis[t]==dis[x]+a[i].v&&mx[t]>(x==vs?0:max(mx[x],x))) mx[t]=(x==vs?0:max(mx[x],x));
        }
    }
    for (int i=1;i<=n;i++) if (i!=vs) ans+=mx[i];
}

inline void gao()
{
    n=rd();m=rd();
    memset(head,0,sizeof(head));
    tot=0;
    for (int i=1;i<=m;i++)
    {
        int x=rd(),y=rd(),z=rd();
        add(x,y,z);add(y,x,z);
    }
    ans=0;
    for (int i=1;i<=n;i++) work(i);
    printf("%lld\n",ans%998244353);
}

int main()
{
    t=rd();
    while (t--) gao();
    return 0;
}