> #include<vector>
> #include<cmath>
> #include<cstring>
> #include<algorithm>
> #include<string>
> #include<cstdio>
> #include<iostream>
> #include<queue>
> #define MT(x,i) memset(x,i,sizeof(x))
> using namespace std;
> typedef long long LL;
> 
> const int MAXN=1000005;
> const LL INF=100000000000LL;
> int input_a[MAXN],input_b[MAXN],input_c[MAXN];//储存输入
> struct Edge
> {
>     int v;
>     LL cost;
>     Edge(int _v=0,LL _cost=0):v(_v),cost(_cost) {}
> };
> vector<Edge>E[MAXN];
> void addedge(int u,int v,LL w)
> {
>     E[u].push_back(Edge(v,w));
> }
> bool vis[MAXN];//在队列标志
> int cnt[MAXN];//每个点的入队列次数
> LL dist[MAXN];
> bool SPFA(int start,int n)
> {
>     memset(vis,false,sizeof(vis));
>     for(int i=1; i<=n; i++)dist[i]=INF;
>     vis[start]=true;
>     dist[start]=0;
>     queue<int>que;
>     while(!que.empty())que.pop();
>     que.push(start);
>     memset(cnt,0,sizeof(cnt));
>     cnt[start]=1;
>     while(!que.empty())
>     {
>         int u=que.front();
>         que.pop();
>         vis[u]=false;
>         for(int i=0; i<E[u].size(); i++)
>         {
>             int v=E[u][i].v;
>             if(dist[v]>dist[u]+E[u][i].cost)
>             {
>                 dist[v]=dist[u]+E[u][i].cost;
>                 if(!vis[v])
>                 {
>                     vis[v]=true;
>                     que.push(v);
>                     if(++cnt[v]>n)return false;//cnt[i]为入队列次数，用来判定是否存在负环回路
>                 }
>             }
>         }
>     }
>     return true;
> }
> int main()
> {
>     int n,m,cas,a,b,c;
>     scanf("%d",&cas);
>     while(cas--)
>     {
>         scanf("%d%d",&n,&m);
>         for(int i=0;i<m;++i){
>             scanf("%d%d%d",&a,&b,&c);
>             addedge(a,b,c);
>             input_a[i]=a,input_b[i]=b,input_c[i]=c;
>         }
>         LL sum=0;
>         SPFA(1,n);
>         for(int i=2;i<=n;i++) sum+=dist[i];
> 
>         for(int i=0;i<=n;++i) E[i].clear();//将图反向
>         for(int i=0;i<m;++i) addedge(input_b[i],input_a[i],input_c[i]);
>         SPFA(1,n); //再次spfa
>         for(int i=2;i<=n;i++) sum+=dist[i];
> 
>         cout<<sum<<endl;
>     }
>     return 0;
> }