#include<bits/stdc++.h>

#define y1 dmytxdy
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

bool chkmax(int &x,int y){return x<y?x=y,true:false;}
bool chkmin(int &x,int y){return x>y?x=y,true:false;}

int readint(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n,m,tot;
ll v[4005],c[4005],nxt[4005],h[1005],dis[1005],f[1005];
bool vis[1005];
priority_queue<pll> q;

void addedge(int x,int y,int z){
    v[++tot]=y; c[tot]=z; nxt[tot]=h[x]; h[x]=tot;
    v[++tot]=x; c[tot]=z; nxt[tot]=h[y]; h[y]=tot;
}

void dij(int st){
    memset(dis,0x3f,sizeof(dis));
    memset(f,0x3f,sizeof(f));
    memset(vis,false,sizeof(vis));
    dis[st]=f[st]=0; q.push(mp(0,st));
    while(!q.empty()){
        ll t=q.top().se; q.pop();
        vis[t]=true;
        for(int p=h[t];p;p=nxt[p]){
            if(vis[v[p]]) continue;
            if(dis[v[p]]>dis[t]+c[p]){
                dis[v[p]]=dis[t]+c[p],f[v[p]]=t!=st?max(f[t],t):0;
                q.push(mp(-dis[v[p]],v[p]));
            }
            else if(dis[v[p]]==dis[t]+c[p]) f[v[p]]=t!=st?min(f[v[p]],max(f[t],t)):0;
        }
    }
}

int main(){
    int T=readint();
    while(T--){
        n=readint(); m=readint();
        memset(h,0,sizeof(h)); tot=0;
        int x,y,z;
        for(int i=1;i<=m;i++){
            x=readint(); y=readint(); z=readint();
            addedge(x,y,z);
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            dij(i);
            for(int j=1;j<=n;j++) if(i!=j) ans+=f[j];
//            for(int j=1;j<=n;j++) cout<<f[j]<<' ';
//            cout<<endl;
//            for(int j=1;j<=n;j++) cout<<dis[j]<<' ';
//            cout<<endl;
        }
        printf("%d\n",ans);
    }
    return 0;
}