之前一直觉得网络流是一个非常高端很难学的东西，感觉以自己的水平可能一辈子都不会去学这么难的东西了，感谢BUPT这次多校中把最大流作为签到题，强迫我去学了一波，看了很久，过程也非常艰难，最终还是把这道题给补出来了。看到自己的进步还是很开心的，也许这就是玩算法竞赛的意义吧.

这一道题目的目的是要求通过删掉一些边，使得图中1到n的最短路边长，求删除边的最小权值和。简单分析一下，1到n可能有多条最短路，不在这些最短路上的边对最短路没有贡献，对题目无用，所以直接忽略。于是题目转化成求1到n所有最短路组成的新的一幅图的最小割，建立新图时用dijkstra算出所有点到1的最短路dis[i]，对满足dis[x]+dis[y]+边权值(x->y)的x和y，这两点一定在新的图中。学了网络流之后知道，最小割>=最大流，在图为残余网络的时候等号成立。这道题目就变成求两点间的最短路集合，然后上最大流的板子(https://blog.nowcoder.net/n/9862adc1f52c4c78aa54f62361eb90b1)。

代码: 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct Edge1 {
	int to,Next; ll w;
}edge[maxn<<1];
int n,tot,num,head[maxn],layer[maxn],ver[maxn],nxt[maxn],hd[maxn],vis[maxn];
ll dis[maxn],e[maxn];
ll max(ll a,ll b){return a>b?a:b;};
ll min(ll a,ll b){return a<b?a:b;};
void ADD(int x,int y,ll z)
{
	ver[++num]=y,e[num]=z,nxt[num]=hd[x],hd[x]=num;
}
void add(int x,int y,ll z)
{
	edge[++tot].to=y,edge[tot].w=z,edge[tot].Next=head[x],head[x]=tot;
	edge[++tot].to=x,edge[tot].w=0,edge[tot].Next=head[y],head[y]=tot;
}
void Dijkstra(int s)
{
	priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > PQ;
	PQ.push(make_pair(0,s));
	for(int i=1;i<=n;i++) vis[i]=0,dis[i]=INF;
	dis[s]=0;
	while(!PQ.empty())
	{
		ll z;
		int x=PQ.top().second,y; PQ.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=hd[x];i;i=nxt[i]) {
			y=ver[i],z=e[i];
			if(dis[y]>dis[x]+z)
			{
				dis[y]=dis[x]+z;
				PQ.push(make_pair(dis[y],y));
			}
		}
	}
}
bool bfs(int s,int t)
{
	for(int i=1;i<=n;i++) layer[i]=-1;
	layer[s]=0;
	queue<int> q; q.push(s);
	while(!q.empty())
	{
		int x=q.front(),y; q.pop();
		for(int i=head[x];i;i=edge[i].Next) {
			y=edge[i].to;
			if(edge[i].w&&layer[y]==-1) 
			{
				layer[y]=layer[x]+1;
				q.push(y);
				if(y==t) return true;
			}
		}
	}
	return false;
}
ll Dinic(int x,int t,ll flow)
{
	if(x==t) return flow;
	ll rest=flow,k; int y;
	for(int i=head[x];i&&rest;i=edge[i].Next) {
		y=edge[i].to;
		if(edge[i].w&&layer[y]==layer[x]+1)
		{
			k=Dinic(y,t,min(rest,edge[i].w));
			if(!k) layer[y]=-1;
			edge[i].w-=k;
			edge[i^1].w+=k;
			rest-=k;
		}
	}
	return flow-rest;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int m,x,y; ll z;
		scanf("%d%d",&n,&m);
		tot=1,num=0;
		for(int i=1;i<=n;i++) head[i]=0;
		for(int i=1;i<=m;i++) {
			scanf("%d%d%lld",&x,&y,&z);
			ADD(x,y,z);
		}
		Dijkstra(1);
		if(dis[n]==INF) {
			printf("0\n"); continue;
		}
		for(int i=1;i<=n;i++) {
			x=i;
			for(int j=hd[x];j;j=nxt[j])
			{
				y=ver[j];
				if(dis[x]+e[j]==dis[y])
					add(x,y,e[j]);
			}
		}
		ll flow=0,maxflow=0;
		while(bfs(1,n)) while(flow=Dinic(1,n,INF))
			maxflow+=flow;
		printf("%lld\n",maxflow);
	}
	return 0;
}