#pragma comment(linker, "/STACK:102400000,102400000")
//#include<bits/stdc++.h>
#include <ctime>
#include <iostream>
#include <assert.h>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define fi first
#define se second
#define endl '\n'
#define o2(x) (x)*(x)
#define BASE_MAX 31
#define mk make_pair
#define eb push_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a),(b),sizeof((a)))
#define iis std::ios::sync_with_stdio(false); cin.tie(0)
#define my_unique(x) sort(all(x)),x.erase(unique(all(x)),x.end())
using namespace std;
#pragma optimize("-O3")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> pii;
inline LL read() {
    LL x = 0;int f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x = f ? -x : x;
}
inline void write(LL x, bool f) {
    if (x == 0) {putchar('0'); if(f)putchar('\n');else putchar(' ');return;}
    if (x < 0) {putchar('-');x = -x;}
    static char s[23];
    int l = 0;
    while (x != 0)s[l++] = x % 10 + 48, x /= 10;
    while (l)putchar(s[--l]);
    if(f)putchar('\n');else putchar(' ');
}
int lowbit(int x) { return x & (-x); }
template<class T>T big(const T &a1, const T &a2) { return a1 > a2 ? a1 : a2; }
template<class T>T sml(const T &a1, const T &a2) { return a1 < a2 ? a1 : a2; }
template<typename T, typename ...R>T big(const T &f, const R &...r) { return big(f, big(r...)); }
template<typename T, typename ...R>T sml(const T &f, const R &...r) { return sml(f, sml(r...)); }
void debug_out() { cerr << '\n'; }
template<typename T, typename ...R>void debug_out(const T &f, const R &...r) {cerr << f << " ";debug_out(r...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);

const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int HMOD[] = {1000000009, 1004535809};
const LL BASE[] = {1572872831, 1971536491};
const int mod = 998244353;//998244353
const int MOD = 2e9 + 7;
const int INF = 2e9 + 7;
const int MXN = 1e3 + 7;
const int MXE = 4e5 + 7;
int n,m;
LL mn[MXN][MXN];
int dp[MXN][MXN];
vector<pii> mp[MXN];
struct lp{
    int w, v, id;
    friend bool operator<(const lp&a, const lp&b) {
        return a.w > b.w;
    }
}A, B;
int ck(int x, int y) {
    if(x == y) return 0;
    return x;
}
void dij(int x) {
    priority_queue<lp> Q;
    A.w = 0; A.v = x;A.id = x;
    Q.push(A);
    while(!Q.empty()) {
        A = Q.top(); Q.pop();
        int len = mp[A.v].size();
        for(int i = 0; i < len; ++i) {
            int v = mp[A.v][i].fi, w = mp[A.v][i].se;
//            debug(x, A.v, v, mn[x][v], mn[x][A.v], w)
            if(mn[x][v] > mn[x][A.v] + w) {
                mn[x][v] = mn[x][A.v] + w;
                dp[x][v] = big(ck(dp[x][A.v],x), ck(A.v, x));
                B.w = mn[x][v], B.v = v;
                Q.push(B);
            }else if(mn[x][v] == mn[x][A.v] + w && dp[x][v] > big(ck(dp[x][A.v],x), ck(A.v, x))) {
                dp[x][v] = big(ck(dp[x][A.v],x), ck(A.v, x));
                B.w = mn[x][v], B.v = v;
                Q.push(B);
            }
        }
    }
}
int main() {
    int tim = read();
    while(tim --) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) mn[i][j] = INFLL, dp[i][j] = INF;
            mn[i][i] = 0;
            dp[i][i] = 0;
            mp[i].clear();
        }
        for(int i = 1, a, b, c; i <= m; ++i) {
            a = read(), b = read(), c = read();
            mp[a].eb(mk(b, c));
            mp[b].eb(mk(a, c));
//            mn[a][b] = mn[b][a] = sml(mn[b][a], c);
        }
        for(int i = 1; i <= n; ++i) {
            dij(i);
        }
//        for(int i = 1; i <= n; ++i) {
//            for(int j = 1; j <= n; ++j) printf("%d ", dp[i][j]);
//            printf("\n");
//        }
        LL ans = 0;
        for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) ans = (ans + dp[i][j])%mod;
        printf("%I64d\n", ans);
    }
#ifndef ONLINE_JUDGE
//    cout << "time cost:" << 1.0*clock()/CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}
/*做法1：
 * 建超级源汇点求出可行流，残余网络上求TS最大流，两者相减
 * 做法2：
 * 建超级源汇点求出可行流
 * */