#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int mn=1e5+5;
struct edge
{
    int u,v,w;
}a[mn];
int f[mn],sz[mn],ans;
bool cmp(edge x,edge y)
{
    return x.w<y.w;
}
int find(int x)
{
    return (f[x]==x)?x:f[x]=find(f[x]);
}
int n,m;
void solve()
{
    ans=0;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].w);
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(a[i].u)==find(a[i].v))continue;
        ans+=sz[find(a[i].u)]*sz[find(a[i].v)]*a[i].w;
        sz[find(a[i].v)]+=sz[find(a[i].u)];
        f[find(a[i].u)]=find(a[i].v);
    }
    printf("%lld\n",ans);
}
signed main()
{
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        solve();
    }
}