> #include<stdio.h>
> #include<string.h>
> #define M 1000005
> #define INF 0xfffffff
> 
> int n,m;
> int dis1[M];
> int dis2[M];
> int que[M*10];
> bool inq[M];
> int head1[M];
> int head2[M];
> int tot1,tot2;
> 
> struct node
> {
> 	int to,v,next;
> }edge1[M],edge2[M];
> 
> void add1(int a,int b,int c)
> {
> 	edge1[tot1].to=b; edge1[tot1].v=c;
> 	edge1[tot1].next=head1[a]; head1[a]=tot1++;
> }
> 
> void add2(int a,int b,int c)
> {
> 	edge2[tot2].to=b; edge2[tot2].v=c;
> 	edge2[tot2].next=head2[a]; head2[a]=tot2++;
> }
> 
> void SPFA_1()
> {
> 	int i,p;
> 	int r=0,l=0;
> 	for(i=1;i<=n;i++)
> 	{
> 		dis1[i]=INF;
> 		inq[i]=false;
> 	}
> 	dis1[1]=0;
> 	que[r++]=1;
> 	inq[1]=true;
> 	while(l<r)
> 	{
> 		p=que[l++];
> 		inq[p]=false;
> 		for(i=head1[p];i!=-1;i=edge1[i].next)
> 		{
> 			int u=edge1[i].to;
> 			if(dis1[u]>dis1[p]+edge1[i].v)
> 			{
> 				dis1[u]=dis1[p]+edge1[i].v;
> 				if(!inq[u])
> 				{
> 					inq[u]=true;
> 					que[r++]=u;
> 				}
> 			}
> 		}
> 	}
> }
> 
> void SPFA_2()
> {
> 	int i,p;
> 	int r=0,l=0;
> 	for(i=1;i<=n;i++)
> 	{
> 		dis2[i]=INF;
> 		inq[i]=false;
> 	}
> 	dis2[1]=0;
> 	que[r++]=1;
> 	inq[1]=true;
> 	while(l<r)
> 	{
> 		p=que[l++];
> 		inq[p]=false;
> 		for(i=head2[p];i!=-1;i=edge2[i].next)
> 		{
> 			int u=edge2[i].to;
> 			if(dis2[u]>dis2[p]+edge2[i].v)
> 			{
> 				dis2[u]=dis2[p]+edge2[i].v;
> 				if(!inq[u])
> 				{
> 					inq[u]=true;
> 					que[r++]=u;
> 				}
> 			}
> 		}
> 	}
> }
> 
> int main()
> {
> 	int cas,i;
> 	int a,b,c;
> 	__int64 sum;
> 	scanf("%d",&cas);
> 	while(cas--)
> 	{
> 		scanf("%d%d",&n,&m);
> 		for(i=1;i<=n;i++)
> 			head1[i]=head2[i]=-1;
> 		tot1=tot2=0;
> 		while(m--)
> 		{
> 			scanf("%d%d%d",&a,&b,&c);
> 			add1(a,b,c);
> 			add2(b,a,c);
> 		}	
> 		SPFA_1();
> 		sum=0;
> 		for(i=1;i<=n;i++)
> 			sum+=dis1[i];
> 		SPFA_2();
> 		for(i=1;i<=n;i++)
> 			sum+=dis2[i];
> 		printf("%I64d\n",sum);
> 	}
> 	return 0;
> }