#include<bits/stdc++.h>
#include<vector>
using namespace std;
const int mx = 2e3+5;
const long long mo = 998244353;

typedef struct Node
{
    int x;
    long long d;
    long long k;
    Node(int a, long long b, long long c) {x = a;d = b; k = c;}
    bool operator<(const Node& a) const
    {
        if (d == a.d) return k>a.k;//
        return d > a.d;
    }
}Eage;
 priority_queue<Node> q;

 long long dis[mx];
 bool vs[mx];

 vector<Node>g[mx];

int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        int n,m;
        cin>>n>>m;
        for (int i=1;i<=n;i++) g[i].clear();
        while (m--)
        {
            int x,y;
            long long w;
            cin>>x>>y>>w;
            g[x].push_back(Node(y,w,0));
            g[y].push_back(Node(x,w,0));
        }
        long long ans = 0;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                dis[j] = 100000000000000000;
                vs[j] = false;
            }
            dis[i] = 0;
            q.push(Node(i,0, 0));
            while (!q.empty())
            {
                Node w = q.top();
                q.pop();
                if (vs[w.x]) continue;
                vs[w.x] = true;
                ans = (ans+w.k)%mo;
                for (int j=0;j<g[w.x].size();j++)
                {
                    Node wk = g[w.x][j];
                    if (dis[wk.x] >= dis[w.x] + wk.d)
                    {
                        dis[wk.x] = dis[w.x] + wk.d;
                        long long kk=w.x;
                        if (w.x==i)
                        {
                            kk =0;
                        }
                        kk = max(w.k, kk);
                        q.push(Node(wk.x, dis[wk.x], kk));
                    }
                }
            }
        }
        cout<<ans<<endl;

    }

}