#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<cmath>
#include<string>
#include<map>
#include<vector>
#include<ctime>
#include<stack>
using namespace std;
#define mm(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const long long mod = 998244353;
const int maxn = 2010;
const ll inf = 1e18;
int a[maxn][maxn], n, m;
int vis[maxn];
ll dis[maxn];
struct node {
    int v;
    ll w;
    friend bool operator <(node a, node b) {
        return a.w > b.w;
    }
};
vector<node>g[maxn];
void dijkstra(int u) {
    priority_queue<node>q;
    for (int i = 1; i <= n; ++i) { dis[i] = inf; vis[i] = 0; }
    dis[u] = 0;
    for (int i = 0; i < g[u].size(); i++)
    {
        q.push(node{ g[u][i].v,g[u][i].w });
        dis[g[u][i].v] = min(g[u][i].w, dis[g[u][i].v]);
    }
    int x, y;
    ll z;
    while (!q.empty())
    {
        x = q.top().v;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = 0; i < g[x].size(); i++)
        {
            y = g[x][i].v, z = g[x][i].w;
            if (dis[y] > dis[x] + z)
            {
                a[u][y] = max(a[u][x], x);
                dis[y] = dis[x] + z;
                q.push(node{ y,dis[y] });
            }
            else if (dis[y] == dis[x] + z)
                a[u][y] = min(a[u][y], max(a[u][x], x));
        }
    }
}
int main()
{
    int t, x, y;
    ll w;
    ll ans;
    cin >> t;
    while (t--)
    {
        mm(a, 0);
        ans = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) g[i].clear();
        while (m--)
        {
            scanf("%d%d%I64d", &x, &y, &w);
            if (x == y) continue;
            g[x].push_back(node{ y,w });
            g[y].push_back(node{ x,w });
        }
        for (int i = 1; i <= n; ++i)
            dijkstra(i);
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                ans = (ans + a[i][j]) % mod;
            }
        }
        printf("%I64d\n", ans);
    }
}

/*
4 4
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 1 1000000000
*/