#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=2147483647;
int cnt=1,head[114514],n,m,s,t,dp[11451],gp[114514],ans;
struct dian{
	int v,nxt,val;
}nd[114514];
void add(int u,int v,int w){
	nd[++cnt].v=v;
	nd[cnt].val=w;
	nd[cnt].nxt=head[u];
	head[u]=cnt;
}
void bfs(){
	memset(dp,-1,sizeof dp);
	memset(gp,0,sizeof gp);
	dp[t]=0;
	gp[1]=1;
	queue<int>q;
	q.push(t);
	while(q.size()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=nd[i].nxt){
			int v=nd[i].v;
			if(dp[v]!=-1) continue;
			q.push(v);
			dp[v]=dp[u]+1;
			gp[dp[v]]++;
		}
	}
}
int dfs(int u,int fl){
	if(u==t){
		ans+=fl;
		return fl;
	}
	int us=0;
	for(int i=head[u];i;i=nd[i].nxt){
		int d=nd[i].v;
		if(nd[i].val&&dp[d]+1==dp[u]){
			int mn=dfs(d,min(nd[i].val,fl-us));
			if(mn){
				nd[i].val-=mn;
				nd[i^1].val+=mn;
				us+=mn;
			}
			if(us==fl) return us;
		}
	}
	gp[dp[u]]--;
	if(!gp[dp[u]]) dp[s]=n+1;
	dp[u]++;
	gp[dp[u]]++;
	return us;
}
int nb_isap(){
    ans=0;
	bfs();
	while(dp[s]<n) dfs(s,inf);
	return ans;
}
signed main(){
	cin>>n>>m;s=1;
	t=n;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,0);
	}
	cout<<nb_isap();
}

代码从板子拷过来的