#include <bits/stdc++.h>
using namespace std;
const long long inf=0x3f3f3f3f3f3f3f3f;
const long long mod=998244353;
const int maxn=1123;
typedef pair<long long,int> pli;
typedef pair<int,int> pii;
int T,n,m,pre[maxn];
long long res,d[maxn];
vector<pii> G[maxn];
inline void solve(int uu) {
    priority_queue<pli,vector<pli>,greater<pli> > que;
    que.push(pli(0,uu));
    d[uu]=pre[uu]=0;
    for (int i=1;i<=n;++i) if (i!=uu) d[i]=inf;
    while (!que.empty()) {
        int u=que.top().second;
        long long o=que.top().first;
        que.pop();
        if (o>d[u]) continue;
        for (int i=0;i<(int)G[u].size();++i) {
            int v=G[u][i].first;
            int e=G[u][i].second;
            if (d[v]>d[u]+e) {
                d[v]=d[u]+e;
                int tmp=(u!=uu)?u:0;
                pre[v]=max(pre[u],tmp);
                que.push(pli(d[v],v));
            } else if (d[v]==d[u]+e) {
                int tmp=(u!=uu)?u:0;
                pre[v]=min(pre[v],max(pre[u],tmp));
            }
        }
    }
    for (int i=1;i<=n;++i)
        res+=pre[i];
}
int main()
{
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;++i) G[i].clear();
        for (int i=0;i<m;++i) {
            int u,v,w;scanf("%d%d%d",&u,&v,&w);
            G[u].push_back(pii(v,w));
            G[v].push_back(pii(u,w));
        }
        res=0;
        for (int i=1;i<=n;++i) solve(i);
        cout<<res%mod<<endl;
    }
    return 0;
}