#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=lst[a];i;i=nxt[i])
#define pb(a) push_back(a)
using namespace std;

typedef long long ll;

const int N=4e3+5,Mo=998244353;
const ll inf=1e15;

int t[N],nxt[N],val[N],lst[N],l;
void add(int x,int y,int z) {t[++l]=y;val[l]=z;nxt[l]=lst[x];lst[x]=l;}

int ty,n,m,u[N],v[N],z[N],q[N<<5],deg[N],f[N];
ll dis[N];
bool vis[N];
vector<int> to[N],fr[N];

void spfa(int S) {
    fo(i,1,n) dis[i]=inf;dis[S]=0;
    int i=0,j=1;q[1]=S;vis[S]=1;
    while (i<j) {
        rep(k,q[++i])
            if (dis[t[k]]>dis[q[i]]+val[k]) {
                dis[t[k]]=dis[q[i]]+val[k];
                if (!vis[t[k]]) q[++j]=t[k],vis[t[k]]=1;
            }
        vis[q[i]]=0;
    }
}

int main() {
    for(scanf("%d",&ty);ty;ty--) {
        scanf("%d%d",&n,&m);
        l=0;fo(i,1,n) lst[i]=0;
        fo(i,1,m) {
            scanf("%d%d%d",&u[i],&v[i],&z[i]);
            add(u[i],v[i],z[i]);add(v[i],u[i],z[i]);
        }
        int ans=0;
        fo(i,1,n) {
            spfa(i);
            fo(j,1,n) to[j].clear(),fr[j].clear(),deg[j]=0;
            fo(j,1,m) {
                int x=u[j],y=v[j];
                if (dis[x]==dis[y]+z[j]) to[y].pb(x),fr[x].pb(y),deg[x]++;
                if (dis[y]==dis[x]+z[j]) to[x].pb(y),fr[y].pb(x),deg[y]++;
            }
            int hd=0,tl=0;
            fo(j,1,n) if (!deg[j]) q[++tl]=j;
            while (hd<tl) {
                int x=q[++hd];
                if (to[x].empty()) continue;
                for(int j=0;j<to[x].size();j++) {
                    int y=to[x][j];
                    if (!(--deg[y])) q[++tl]=y;
                }
            }
            fo(j,1,n) f[j]=n+1;f[i]=0;
            fo(j,1,tl) {
                int x=q[j];
                if (x==i) continue;
                if (fr[x].empty()) continue;
                for(int k=0;k<fr[x].size();k++) {
                    int y=fr[x][k];
                    f[x]=min(f[x],y==i?0:max(f[y],y));
                }
                ans+=f[x];
            }
        }
        printf("%d\n",ans%Mo);
    }
    return 0;
}