边取反，从汇点跑单源最短路即可。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define MAXN 1111111
#define MAXM 1111111 inline void in(int &ret){
char c; ret=;
while(c=getchar(),c<''||c>'');
while(c>=''&&c<='') ret=ret*+c-'',c=getchar();
}
void out(long long x){
if(x>) out(x/);
putchar(x%+'');
} struct Edge{
int v,cost,next;
}edge[MAXM<<];
int head[MAXN],rhead[MAXN],NE;
void addEdge(int a,int b,int c){
edge[NE].v=b; edge[NE].cost=c; edge[NE].next=head[a];
head[a]=NE++;
edge[NE].v=a; edge[NE].cost=c; edge[NE].next=rhead[b];
rhead[b]=NE++;
} int n,m;
int d[MAXN];
bool vis[MAXN];
void SPFA(){
memset(d,,sizeof(d));
d[]=;
memset(vis,,sizeof(vis));
vis[]=;
queue<int> que;
que.push();
while(!que.empty()){
int u=que.front(); que.pop();
for(int i=head[u];i !=-; i=edge[i].next){
int v=edge[i].v;
if(d[v]>d[u]+edge[i].cost){
d[v]=d[u]+edge[i].cost;
if(!vis[v]){
vis[v]=;
que.push(v);
}
}
}
vis[u]=;
}
}
void rSPFA(){
memset(d,,sizeof(d));
d[]=;
memset(vis,,sizeof(vis));
vis[]=;
queue<int> que;
que.push();
while(!que.empty()){
int u=que.front(); que.pop();
for(int i=rhead[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(d[v]>d[u]+edge[i].cost){
d[v]=d[u]+edge[i].cost;
if(!vis[v]){
vis[v]=;
que.push(v);
}
}
}
vis[u]=;
}
} int main(){
int t,a,b,c;
in(t);
while(t--){
NE=;
memset(head,-,sizeof(head));
memset(rhead,-,sizeof(rhead));
in(n); in(m);
while(m--){
in(a); in(b); in(c);
addEdge(a,b,c);
}
long long res=;
SPFA();
for(int i=; i<=n; ++i) res+=d[i];
rSPFA();
for(int i=; i<=n; ++i) res+=d[i];
out(res); putchar('\n');
}
return ;
}