#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e3 + 70;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353;
const double eps = 1e-7;
const double PI = acos(-1.0);

int n, m, k;

struct Edge{
    int from, to, dist;

    Edge(int u, int v, int w) :from(u), to(v), dist(w){};
};

struct HeapNode{
    int id; ll dist;

    HeapNode(int u, ll d) :id(u), dist(d){};

    bool operator < (const HeapNode& rhs) const{ return dist > rhs.dist; }
};

struct Dijkstra{
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    ll d[maxn];
    int mi[maxn];
    bool done[maxn];

    // 0 ... n
    void init(int n){
        this->n = n;
        edges.clear();
        for (int i = 0; i < n; i++) G[i].clear();
    }

    //directed
    void AddEdge(int u, int v, int w){
        edges.push_back(Edge(u, v, w));
        m = edges.size();
        G[u].push_back(m - 1);
    }

    void dijkstra(int s){
        priority_queue<HeapNode> Q;
        for (int i = 0; i < n; i++){
            d[i] = inf;
            mi[i] = done[i] = 0;
        }
        d[s] = 0;
        Q.push(HeapNode(s, d[s]));
        while (!Q.empty()){
            HeapNode x = Q.top(); Q.pop();
            int u = x.id;
            if (done[u]) continue;
            done[u] = true;

            for (int i = 0; i < G[u].size(); i++){
                Edge& e = edges[G[u][i]];
                if (d[e.to] > d[u] + e.dist){
                    d[e.to] = d[u] + e.dist;
                    if(u != s) mi[e.to] = max(mi[u], u+1);
                    Q.push(HeapNode(e.to, d[e.to]));
                }
                else if(d[e.to] == d[u] + e.dist){
                    if(u != s) mi[e.to] = min(mi[e.to], max(mi[u], u+1));
                    else mi[e.to] = 0;
                }
            }
        }
    }

    int solve(){
        int ans = 0;
        for(int i=0;i<n;i++){
            dijkstra(i);
            for(int j=0;j<n;j++){
                ans=(ans + mi[j])%MOD;
                //cout<<i+1<<" "<<j+1<<": "<<mi[j]<<endl;
            }
        }
        return ans;
    }
};

Dijkstra Solver;

int main(){
    //freopen("in.txt", "r", stdin);
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        Solver.init(n);
        for(int i=0;i<m;i++){
            int u, v, w;
            scanf("%d %d %d",&u,&v,&w);
            u--; v--;
            Solver.AddEdge(u,v,w);
            Solver.AddEdge(v,u,w);
        }

        int ans = Solver.solve();
        printf("%d\n",ans);
    }
    return 0;
}