#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <sstream>
using namespace std;


long long w[1001][1001];
int cnt[1001][1001];

void process()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        w[i][i] = 0;
        for (int j = i + 1; j <= n; ++j) {
            w[i][j] = w[j][i] = 1000000000LL * 3000;
        }
    }

    memset(cnt, 0, sizeof(cnt));

    int a, b, v;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> v;
        if (v < w[a][b]) {
            w[a][b] = w[b][a] = v;
        }
    }

    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) {
            if (w[i][k] + w[k][j] < w[i][j]) {
                w[i][j] = w[i][k] + w[k][j];
                cnt[i][j] = k;

                w[j][i] = w[i][j];
                // cnt[j][i] = k;
            }
        }
    }

    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            // cout << i << ' ' << j << ' ' << cnt[i][j] << ' ' << w[i][j] << endl;
            res += cnt[i][j];
        }
    }

    res *= 2;
    res %= 998244353LL;
    cout << res << endl;
}

int main(void)
{
    int T;
    cin >> T;
    for (int i = 1; i <= T; ++i)
    {
        process();
    }
    return 0;
}