#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; const int inf=1<<24; const int N=1000000+5; struct node { int to,w; node* next; }; node* edge[N]; node* reedge[N]; int n,m,x,dist[N],inq[N],q[N]; void spfa(int flag) { int i,u,h=0,t=1; node* ptr; for(i=0; i<=n; i++) { dist[i]=inf; inq[i]=0; } dist[1]=0; inq[1]=1; q[0]=1; while(h!=t) { u=q[h]; h++; inq[u]=0; if(flag==1) ptr=edge[u]; else ptr=reedge[u]; while(ptr) { if(dist[ptr->to]>(dist[u]+ptr->w)) { dist[ptr->to]=dist[u]+ptr->w; if(inq[ptr->to]==0) { q[t]=ptr->to; t++; inq[ptr->to]=1; } } ptr=ptr->next; } } } int main() { int cas,i,u,v,w,ans; scanf("%d",&cas); while(cas--) { scanf("%d%d",&n,&m); for(i=1; i<=n; i++) { edge[i]=NULL; reedge[i]=NULL; } for(i=0; i
       
        to=u; temp->w=w; temp->next=NULL; if(edge[v]==NULL) { edge[v]=temp; } else { temp->next=edge[v]; edge[v]=temp; } temp= new node; temp->to=v; temp->w=w; temp->next=NULL; if(reedge[u]==NULL) { reedge[u]=temp; } else { temp->next=reedge[u]; reedge[u]=temp; } } ans=0; spfa(1); for(i=2; i<=n; i++) { //printf("%d\n",dist[i]); ans+=dist[i]; } spfa(0); for(i=2; i<=n; i++) { ans+=dist[i]; } printf("%d\n",ans); } return 0; }