#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
//head
#define N 1100
#define M 4100
int head[N];
int v[M],cost[M],Next[M];
ll dis[N];
int n,m,num=0,lab[N],maxlab[N];
bool vis[N];
struct node{
    int id,maxlab;
    ll dis;
};
bool operator > (node a, node b){
    return a.dis<b.dis || (a.dis==b.dis && a.maxlab<b.maxlab);
}
bool operator < (node a, node b){
    return a.dis>b.dis || (a.dis==b.dis && a.maxlab>b.maxlab);
}
bool operator == (node a, node b){
    return a.dis==b.dis || a.maxlab==b.maxlab;
}
priority_queue<node> q;
void add(int x,int y,int z){
    v[++num]=y;
    Next[num]=head[x];
    head[x]=num;
    cost[num]=z;
}
int dij(int st){
    rep(i,1,n){
        lab[i]=i;
        dis[i]=1LL<<60;
        maxlab[i]=n+1;
        vis[i]=1;
    }
    lab[st]=0;
    dis[st]=0;
    maxlab[st]=0;
    while(!q.empty())q.pop();
    q.push((node){st,0,0});
    while(!q.empty()){
        node u=q.top();
        q.pop();
        if(!vis[u.id])continue;
        vis[u.id]=0;
        for(int i=head[u.id];i;i=Next[i]){
            ll t1=dis[u.id]+cost[i];
            int t2 = max(u.maxlab, lab[u.id]);
            if(t1<dis[v[i]] || (t1==dis[v[i]] && t2<maxlab[v[i]])){
                dis[v[i]]=t1;
                maxlab[v[i]]=t2;
                node tmp;
                tmp.id=v[i];
                tmp.dis=dis[v[i]];
                tmp.maxlab=maxlab[v[i]];
                q.push(tmp);
            }
        }
    }
    int ans=0;
    rep(i,1,n)ans+=maxlab[i];
    return ans;
}
void solved(){
    n = read(),m=read();
    num=0;
    rep(i,1,n)head[i]=0;
    rep(i,1,m){
        int x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,z);
    }
    ll ans = 0;
    rep(i,1,n)ans+=dij(i);
    cout<<ans% 998244353<<endl;
}
int main(){
    int T=read();
    while(T--)solved();
    return 0;
}