//#include <bits/stdc++.h>
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstring>
#include<bitset>
//#include <random>

#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define mset(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)

using namespace std;
typedef long long ll;

#ifdef local
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) {
    for (auto x: a)
        cout << x << ' ';
    err(args...);
}
template<typename T, typename... Args>
void err(T a, Args... args) {
    cout << a << ' ';
    err(args...);
}
#else
#define dbg(...)
#endif



template<class T>
inline bool scan(T&ret) {
    char c;
    int sgn;
    if(c=getchar(),c==EOF)
        return 0;
    while(c!='-' and (c<'0' or c>'9'))
        c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0' and c<='9')
        ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}

template<class T>
inline void out(T x) {
    if(x>9)
        out(x/10);
    putchar(x%10+'0');
}


int _ = 0;
void testcase() {
    cout << "Case " << (++_) << ": ";
}

const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const long double eps = 1e-6;
const int mod = 998244353;
//const int maxn = 3e6;
const int N = 1e3+10;
const int M = 710;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int from[N],to[N];
vector<pii>G[N];

int n,m;
ll dis[N];
bool vis[N];

priority_queue<pll,vector<pll>,greater<pll> > q;

ll cal(int s){
    rep1(i,n){
        to[i] = 0;
        from[i]=i;
        dis[i] = INF;
        vis[i] = false;
    }
    vis[s] = true;
    dis[s] = 0;
    for(auto &e:G[s]){
        dis[e.X] = min(dis[e.X],(ll)e.Y);
        q.emplace(e.Y, e.X);
    }
    while(!q.empty()){
        pll now = q.top();q.pop();
        auto &u = now.Y;
        auto &d = now.X;
        if(vis[u] or d != dis[u]) continue;
        vis[u] = true;
        for(auto &e : G[u]){
            auto &w = e.Y;
            auto &v = e.X;
            if(w + d < dis[v]){
                dis[v] = w+d;
                from[v] = max(from[u],v);
                to[v] = from[u];
                q.emplace(dis[v],v);
            }
            else if(w + d == dis[v]){
                from[v] = min(from[v], from[u]);
                from[v] = max(from[v], v);
                to[v] = min(to[v], from[u]);
            }
        }
    }
    ll ans = 0;
    rep1(i,n){
        ans = (ans + to[i]) % mod;
    }
    return ans;
}

void work() {
    cin >> n >> m;
    rep1(i,n){
        G[i].clear();
    }
    rep(i,m){
        int u, v, w;
        cin >> u >> v >> w;
        G[u].EB(v,w);
        G[v].EB(u,w);
    }
    ll ans = 0;
    rep1(i,n){
        ans = (ans + cal(i)) % mod;
    }
    cout << ans << "\n";

}


int main() {
#ifdef local
    freopen("../in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
#endif // local
    IOS;
    int t;
    cin >> t;
    for(;t--;)
        work();
    return 0;
}