#include<iostream>
#include<queue>

using namespace std;

#define SIZE 1000012

struct node
{
    int v;
    long long w;
}edge1[SIZE],edge2[SIZE];
int pre1[SIZE],next1[SIZE];
int pre2[SIZE],next2[SIZE];

class AdjList
{
    public:
        int  Index;
        int  *pre;
        int  *next;
        node *edge;
        AdjList(node *a,int *b,int *c)
        {
            edge=a;
            pre=b;
            next=c;
        }
        void clear(void)
        {
            Index=0;
            memset(pre,-1,sizeof(pre)*SIZE);
            memset(next,-1,sizeof(next)*SIZE);
        }
        void add(int u,int v,long long w)
        {
            edge[Index].v=v;
            edge[Index].w=w;
            next[Index]=pre[u];
            pre[u]=Index++;
        }
        void printInfo(void)
        {
            for(int i=0;Index-i>0;i++)
            {
                for(int j=pre[i];j!=-1;j=next[j])
                {
                    printf("(%d,%d)->%d\t",i,edge[j].v,edge[j].w);
                }
                printf("\n");
            }
        }
};

int tcase;
int n,m;
int x,y;
AdjList a(edge1,pre1,next1);
AdjList b(edge2,pre2,next2);
queue<int> open;
bool inqueue[SIZE];
long long z,dist[SIZE];

void Init(int s0)
{
    open.push(s0);
    memset(dist,0x7f,sizeof(dist)); dist[s0]=0;
    memset(inqueue,false,sizeof(inqueue));
}
void SPFA(AdjList a,int s0)
{
    Init(s0);
    while(!open.empty())
    {
        int u=open.front(); open.pop(); inqueue[u]=false;
        for(int i=a.pre[u];i!=-1;i=a.next[i])
        {
            int v=a.edge[i].v;
            long long w=a.edge[i].w;
            if(dist[v]>dist[u]+w)
            {
                dist[v]=dist[u]+w;
                if(inqueue[v]==false)
                {
                    open.push(v);
                    inqueue[v]=true;
                }
            }
        }
    }
}
long long findAns(void)
{
    long long sum=0;
    SPFA(a,0); for(int i=1;n-i>0;i++) sum+=dist[i];
    SPFA(b,0); for(int i=1;n-i>0;i++) sum+=dist[i];
    return sum;
}
int main()
{
    scanf("%d",&tcase);while(tcase--)
    {
        a.clear();
        b.clear();
        scanf("%d %d",&n,&m);
        for(int i=0;m-i>0;i++)
        {
            scanf("%d %d %I64d",&x,&y,&z);
            a.add(x-1,y-1,z);
            b.add(y-1,x-1,z);   
        }
        printf("%I64d\n",findAns());
    }   
    return 0;
}