#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
#define inf 1000000000000000000ll
long long dis[N]; int fr[N],ans; bool is[N];
int head[N],to[N<<2],nxt[N<<2],val[N<<2],idx,n,m;
void add(int a,int b,int c)
    {nxt[++idx]=head[a],to[idx]=b,val[idx]=c,head[a]=idx;}
void solve()
{
    memset(head,0,sizeof head),idx=ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,z;i<=m;i++)
        scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) dis[j]=inf,fr[j]=0,is[j]=0;
        queue <int> q; dis[i]=0,q.push(i);
        while(!q.empty())
        {
            int p=q.front(); q.pop(),is[p]=false;
            for(int j=head[p];j;j=nxt[j])
                if(dis[to[j]]>dis[p]+val[j])
                {
                    dis[to[j]]=dis[p]+val[j],fr[to[j]]=(p!=i)?max(fr[p],p):0;
                    if(!is[to[j]]) q.push(to[j]),is[to[j]]=true;
                }
                else if(dis[to[j]]==dis[p]+val[j])
                {
                    dis[to[j]]=dis[p]+val[j],fr[to[j]]=min(fr[to[j]],max(fr[p],p));
                    if(!is[to[j]]) q.push(to[j]),is[to[j]]=true;
                }
        }
        for(int j=1;j<=n;j++) ans+=fr[j]/*,printf("%d %d %d\n",i,j,fr[j])*/;
    } printf("%d\n",ans);
}
int main()
{
    int T; scanf("%d",&T);
    while(T--) solve();
}