#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int test,n,m,x,y,z,ct,ord[1111],ans,dp[1111];
long long dist[1111];
vector<pair<int,int> > g[1111];
void dijk(int s)
{
    priority_queue<pair<long long,int> > pq;
    for (int i=1;i<=n;i++) dist[i]=1e18;
    dist[s]=0;
    pq.push(make_pair(0,s));ct=0;
    while(!pq.empty())
    {
        int x=pq.top().second;long long y=-pq.top().first;pq.pop();
        if (dist[x]!=y) continue;
        ord[++ct]=x;
        for (int i=0;i<g[x].size();i++)
        {
            int to=g[x][i].first,val=g[x][i].second;
            if (dist[to]>dist[x]+val)
            {
                dist[to]=dist[x]+val;
                pq.push(make_pair(-dist[to],to));
            }
        }
    }
    dp[s]=0;
    for (int i=2;i<=n;i++)
    {
        dp[ord[i]]=1e9;
        for (int j=0;j<g[ord[i]].size();j++)
        {
            int to=g[ord[i]][j].first,val=g[ord[i]][j].second;
            if (dist[ord[i]]==dist[to]+val) 
            {
                if (to==s) dp[ord[i]]=0;
                else dp[ord[i]]=min(dp[ord[i]],max(dp[to],to));
            }
        }
    }
    for (int i=1;i<=n;i++) ans=(ans+dp[i])%mod;
}
int main()
{
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) g[i].clear();
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            g[x].push_back(make_pair(y,z));
            g[y].push_back(make_pair(x,z));
        }
        ans=0;
        for (int i=1;i<=n;i++)
        {
            dijk(i);
        }
        printf("%d\n",ans);
    }
    return 0;
}