Problem Description
Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.
After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed 1 and go along the shortest path to hers, indexed n.
Now Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl’s home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.
Note, if Jerry can’t reach his girl’s house in the very beginning, the answer is obviously zero. And you don’t need to guarantee that there still exists a way from Jerry’s house to his girl’s after blocking some edges.

Input
The input begins with a line containing one integer T(1≤T≤10), the number of test cases.
Each test case starts with a line containing two numbers n,m(1≤n,m≤10000), the number of houses and the number of one-way roads in the neighbourhood.
m lines follow, each of which consists of three integers x,y,c(1≤x,y≤n,1≤c≤109), denoting that there exists a one-way road from the house indexed x to y of length c.

Output
Print T lines, each line containing a integer, the answer.

Sample Input
1
3 4
1 2 1
2 3 1
1 3 2
1 3 3

Sample Output
3

当时多校的时候，对最小割的了解太片面了，所以导致没有做出来，，，还是太菜了。。。QAQ

这道题怎么做呢？因为题目要求我们不走最短路，所以我们枚举每一条路径，判断是否在最短路里面，最后把最短路的每一条边拿出来，跑一遍最小割即可。这么简单，居然不会QWQ，啊啊啊啊啊！！！

我感觉我的代码应该是最短的，才70多行，别人的都120++

AC代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int T,n,m,tot,cnt,idx,h[N],h1[N],h2[N],head[N],d1[N],d2[N],a[N],b[N],c[N];
struct node{
	int to,w,nex;
}t[N],k[N],p[N];
void add(node *t,int a,int b,int c,int &tot,int *head){
	t[++tot].to=b; t[tot].w=c; t[tot].nex=head[a]; head[a]=tot;
}
void spfa(int *d,int s,int e,node *t,int *head){
	int vis[N]={0};	vis[s]=1;	d[s]=0;
	queue<int> q;	q.push(s);
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=t[i].nex){
			if(d[t[i].to]>d[u]+t[i].w){
				d[t[i].to]=d[u]+t[i].w;
				if(!vis[t[i].to])	vis[t[i].to]=1,q.push(t[i].to);
			}
		}
	}
}
int bfs(){
	memset(h,0,sizeof h);	h[1]=1;	queue<int> q;	q.push(1);
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=p[i].nex){
			if(p[i].w&&!h[p[i].to]){
				h[p[i].to]=h[u]+1;	q.push(p[i].to);
			}
		}
	}	
	return h[n];
}
int dfs(int x,int f){
	if(x==n)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=p[i].nex){
		if(p[i].w&&h[p[i].to]==h[x]+1){
			int mi=dfs(p[i].to,min(f,p[i].w));
			p[i].w-=mi;	p[i^1].w+=mi;	fl+=mi;	f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(1,0x3f3f3f3f);
	return res;
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>m;	tot=idx=cnt=1;	memset(h1,0,sizeof h1);	memset(h2,0,sizeof h2);
		memset(head,0,sizeof head);
		for(int i=1;i<=m;i++){
			cin>>a[i]>>b[i]>>c[i];	add(t,a[i],b[i],c[i],tot,h1);
			add(k,b[i],a[i],c[i],cnt,h2);
		}
		memset(d1,0x3f,sizeof d1);	memset(d2,0x3f,sizeof d2);
		spfa(d1,1,n,t,h1);	spfa(d2,n,1,k,h2);
		for(int i=1;i<=m;i++){
			if(d1[a[i]]+d2[b[i]]+c[i]==d1[n]){
				add(p,a[i],b[i],c[i],idx,head);	add(p,b[i],a[i],0,idx,head);
			}
		}
		cout<<dinic()<<endl;
	}
	return 0;
}