//12252024832524
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
#define Min(x,y) (x<y?x:y)
#define Max(x,y) (x>y?x:y)
using namespace std;

typedef long long LL;
const LL MAXN = 1005;
const LL MOD = 998244353;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL n,m;
LL dis[MAXN],M[MAXN],ans;
struct node
{
    LL v;
    LL s;
    node(){}
    node(LL v1,LL s1){
        v = v1;
        s = s1;
    }
};
struct node1
{
    LL x,MAX;
    LL s;
    node1(){}
    node1(LL x1,LL MAX1,LL s1){
        x = x1;
        MAX = MAX1;
        s = s1;
    }
    bool operator < (const node1 &px)const
    {
        return s >= px.s;
    }
};
vector<node> G[MAXN];

LL Read()
{
    LL x = 0,f = 1;char c = getchar();
    while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
    return x * f;
} 
void Put(LL x)
{
    if(x > 9)
        Put(x/10);
    putchar(x%10^48);
}
void bfs(LL x)
{
    dis[x] = M[x] = 0;
    priority_queue<node1> q;
    q.push(node1(x,0,0));
    while(!q.empty())
    {
        node1 t = q.top();
        q.pop();
        if(t.s > dis[t.x])
            continue;
        LL lenx = G[t.x].size();
        for(LL i = 0;i < lenx;++ i)
        {
            LL jl = t.s + G[t.x][i].s;
            if(jl <= dis[G[t.x][i].v])
            {
                q.push(node1(G[t.x][i].v,Max(G[t.x][i].v,t.MAX),jl));
                if(jl == dis[G[t.x][i].v])
                    M[G[t.x][i].v] = Min(M[G[t.x][i].v],t.MAX);
                else
                    M[G[t.x][i].v] = t.MAX;
                dis[G[t.x][i].v] = jl;
            }
        }
    }
}

int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    for(LL T = Read(); T ;-- T)
    {
        n = Read();
        m = Read();
        ans = 0;
        for(LL i = 1;i <= n;++ i)
            G[i].clear();
        for(LL i = 1;i <= m;++ i)
        {
            LL u = Read(),v = Read();
            LL s = Read();
            G[u].push_back(node(v,s));
            G[v].push_back(node(u,s));
        }
        for(LL i = 1;i <= n;++ i)
        {
            for(LL j = 1;j <= n;++ j)
                dis[j] = M[j] = INF;
            bfs(i);
            for(LL j = 1;j <= n;++ j)
                ans += M[j];
            ans %= MOD;
        }
        Put(ans);
        putchar('\n');
    }
    return 0;
}
/*
1
4 4
1 2 1
2 3 1
3 4 1
1 4 10

ans : 16
*/