/**
 * Author: AcFunction
 * Date:   2019-08-24 13:43:39
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>
#define ll long long
#define db double
#define PII pair <int, int> 
#define pb push_back 
#define fi first
#define se second 
#define MP make_pair

using namespace std;

const int N = 1010; 
const ll INF = 1e18; 
const int mod = 998244353; 

int T, n, m, D[N][N], mn[N], ans, topo[N], ind[N], siz[N], que[N], val[N][N];
ll dis[N][N];

struct edge {
  int v, w; edge *next;
} *h[N], pool[4010], pol[4010], *cur = pool, *curr = pol, *hh[N]; 


struct node {
  int id; ll d; 
  bool operator < (const node &x) const {
    return d > x.d; 
  }
} tmp; 

priority_queue <node> Q; 

void adde(int u, int v, int w) {
  edge *p = cur++; p->v = v; p->w = w; 
  p->next = h[u], h[u] = p; 
}

void addde(int u, int v) {
  edge *p = curr++; p->v = v; 
  p->next = hh[u], hh[u] = p; 
}

void dijkstra(int S) {
  for(int i = 1; i <= n; i++) dis[S][i] = INF, val[S][i] = n + 1; 
  dis[S][S] = 0; val[S][S] = 0; while(!Q.empty()) Q.pop(); Q.push({S, 0}); 
  while(!Q.empty()) {
    tmp = Q.top(); Q.pop(); 
    int u = tmp.id; ll d = tmp.d; 
    if(dis[S][u] < d) continue ; 
    for(edge *p = h[u]; p; p = p->next) {
      int v = p->v; 
      if(dis[S][v] > dis[S][u] + p->w) {
        dis[S][v] = dis[S][u] + p->w; 
        if(u == S) val[S][v] = 0; 
        else val[S][v] = max(u, val[S][u]); 
        tmp.id = v, tmp.d = dis[S][v]; 
        Q.push(tmp); 
      } else {
        if(dis[S][v] == dis[S][u] + p->w) {
          if(val[S][v] > max(u, val[S][u])) {
            if(u == S) val[S][v] = 0; 
            else val[S][v] = max(u, val[S][u]); 
            tmp.id = v, tmp.d = dis[S][v];
            Q.push(tmp); 
          } 
        }
      }
    }
  }
  for(int i = 1; i <= n; i++)   ans += val[S][i], ans %= mod; 
}

int main() {
  scanf("%d", &T); 
  while(T--) {
    ans = 0; 
    scanf("%d %d", &n, &m); cur = pool; 
    for(int i = 1; i <= n; i++) h[i] = 0; 
    for(int i = 1; i <= n; i++) 
      for(int j = 1; j <= n; j++) 
        dis[i][j] = INF, D[i][j] = 0;
    for(int i = 1; i <= n; i++) dis[i][i] = 0;  
    for(int i = 1; i <= m; i++) {
      int u, v; ll w; 
      scanf("%d %d %I64d", &u, &v, &w); 
      adde(u, v, w), adde(v, u, w); 
      dis[u][v] = dis[v][u] = min(dis[u][v], w); 
    }
    for(int i = 1; i <= n; i++) dijkstra(i); 
    printf("%d\n", ans); 
  } 
  return 0; 
}