#include<cstdio> #define Max (0x7FFFFFFFFFFFFFFFLL) #define Maxn (1000001) #define DebugMaxn (1000001) struct edge { int x,y; int next; long long l; }el[DebugMaxn]; int p,q,len; int first[DebugMaxn]; int list[DebugMaxn]; bool v[DebugMaxn]; long long d[DebugMaxn]; long long Ans; void ins(int x,int y,int l) { len+=1; el[len].x=x,el[len].y=y,el[len].l=l; el[len].next=first[x],first[x]=len; return; } void Init() { int x,y; long long l; scanf("%d %d",&p,&q); for(int i=1;i<=p;i++) first[i]=-1; len=0; for(int i=1;i<=q;i++) { scanf("%d %d %I64d",&x,&y,&l); ins(x,y,l); } return; } void Spfa(int st,int ed) { int k,y,x,head,tail; for(int i=1;i<=p;i++) { d[i]=Max; v[i]=false; } v[st]=true; d[st]=0; list[1]=st;head=1;tail=2; while(head<tail) { x=list[head]; k=first[x]; while(k!=-1) { y=el[k].y; if((d[x]+el[k].l)<(d[y])) { d[y]=d[x]+el[k].l; if(!v[y]) { v[y]=true; list[tail]=y; tail+=1; } } k=el[k].next; } v[x]=false; head+=1; } return; } void GetAns() { int a,b,c; Ans=0; Spfa(1,p); for(int i=2;i<=p;i++) { Ans+=d[i]; first[i]=-1; } first[1]=-1; len=0; for(int i=1;i<=q;i++) { a=el[i].x; b=el[i].y; c=el[i].l; ins(b,a,c); } Spfa(1,p); for(int i=2;i<=p;i++) Ans+=d[i]; return; } void Print() { printf("%I64d/n",Ans); return; } int main() { int t; scanf("%d",&t); for(;t>0;t--) { Init(); GetAns(); Print(); } return 0; }
