#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1000005, infi=1<<30;
queue<int> q;
int dist[MAXN];
struct aaa
{
    int u, v, d, next;
} a[MAXN], b[MAXN];
int head1[MAXN], head2[MAXN], tp1, tp2;
void add1(int u,int v,int d)
{
    a[tp1].u=u, a[tp1].v=v, a[tp1].d=d;
    a[tp1].next=head1[u];
    head1[u]=tp1;
    tp1++;
}
void add2(int u,int v,int d)
{
    b[tp2].u=u, b[tp2].v=v, b[tp2].d=d;
    b[tp2].next=head2[u];
    head2[u]=tp2;
    tp2++;
}
int main()
{
    int i, j, t1, n, m, u, v, d;
    scanf("%d",&t1);
    while(t1--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<=m;i++)
            head1[i]=-1, head2[i]=-1;
        tp1=tp2=0;
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&d);
            add1(u,v,d);
            add2(v,u,d);
        }
        for(i=1;i<=n;i++)
            dist[i]=infi;
        dist[1]=0;
        q.push(1);
        while(!q.empty())
        {
            int st=q.front();
            q.pop();
            for(i=head1[st];i>=0;i=a[i].next)
            {
                if(dist[a[i].v]>dist[st]+a[i].d)
                {
                    dist[a[i].v]=dist[st]+a[i].d;
                    q.push(a[i].v);
                }
            }
        }
        long long solv=0;
        for(i=2;i<=n;i++)
            solv+=dist[i];
        for(i=1;i<=n;i++)
            dist[i]=infi;
        dist[1]=0;
        q.push(1);
        while(!q.empty())
        {
            int st=q.front();
            q.pop();
            for(i=head2[st];i>=0;i=b[i].next)
            {
                if(dist[b[i].v]>dist[st]+b[i].d)
                {
                    dist[b[i].v]=dist[st]+b[i].d;
                    q.push(b[i].v);
                }
            }
        }
        for(i=2;i<=n;i++)
            solv+=dist[i];
        printf("%lld\n",solv);
    }
    return 0;
}