#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1005,M=4005,md=998244353;
int T,n,m,u,v,ww,ans;
int fr[N],nxt[M],em[M],w[M],mxe[N];
ll d[N];
bool done[N];
struct node
{
    ll d;
    int mxe;
    int id;
};
bool operator < (node a,node b)
{
    if(a.d==b.d)
        return a.mxe>b.mxe;
    return a.d>b.d;
}
priority_queue<node>q;
inline void addedge(int u,int v,int ww,int i)
{
    nxt[i]=fr[u];
    fr[u]=i;
    em[i]=v;
    w[i]=ww;
}
inline void dijkstra(int s)
{
    memset(d,0x3f,sizeof(d));
    memset(mxe,0x3f,sizeof(mxe));
    memset(done,0,sizeof(done));
    while(!q.empty())
        q.pop();
    d[s]=0;
    mxe[s]=0;
    q.push((node){0,0,s});
    while(!q.empty())
    {
        int x=q.top().id,mxg=q.top().mxe;
        q.pop();
        if(done[x]==0)
            done[x]=1;
        else
            continue;
        for(int j=fr[x];j!=0;j=nxt[j])
            if(d[em[j]]>d[x]+w[j]||(d[em[j]]==d[x]+w[j]&&mxe[em[j]]>mxg))
            {
                d[em[j]]=d[x]+w[j];
                mxe[em[j]]=mxg;
                q.push((node){d[em[j]],max(mxe[em[j]],em[j]),em[j]});
            }
    }
    for(int i=1;i<=n;i++)
        if(i!=s)
            ans=(ans+mxe[i])%md;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(fr,0,sizeof(fr));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&ww);
            addedge(u,v,ww,i*2);
            addedge(v,u,ww,i*2+1);
        }
        ans=0;
        for(int i=1;i<=n;i++)
            dijkstra(i);
        printf("%d\n",ans);
    }
    return 0;
}