#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#define int long long
using namespace std;
inline int read()
{
	int ans=0;char ch=getchar();
	while((ch>'9')||(ch<'0'))ch=getchar();
	while((ch>='0')&&(ch<='9'))ans=ans*10+ch-'0',ch=getchar();
	return ans;
}
int n,m,cnt=1,now[100001],head[100001],to[100001],from[100001],pre[100001],nex[100001],v[100001],dep[100001],gap[100001];
void add(int x,int y,int z){to[++cnt]=y,v[cnt]=z,from[cnt]=x,nex[cnt]=head[x],head[x]=cnt;}
queue<int> q;
int augment()
{
	int k=n,kk=n,flow=999999999999999999;
	while(k!=1)flow=min(flow,v[pre[k]]),k=from[pre[k]];
	while(kk!=1)v[pre[kk]]-=flow,v[pre[kk]^1]+=flow,kk=from[pre[kk]];
	return flow;
}
signed main()
{
	m=read(),n=read();int x,y,z;
	while(m--)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,0);
	q.push(n),dep[n]=1;
	while(!q.empty())
	{
		x=q.front(),q.pop(),++gap[dep[x]];
		for(int i=head[x];i;i=nex[i])
		{
			if(dep[to[i]]==0&&v[i^1])
			dep[to[i]]=dep[x]+1,q.push(to[i]);
		}
	}
	int k=1,flow=0;memcpy(now,head,sizeof(now));
	while(dep[1]<=n)
	{
		if(k==n)flow+=augment(),k=1;
		bool ok=0;
		for(int i=now[k];i;i=nex[i])
		{
			if(v[i]&&dep[to[i]]+1==dep[k])
			{
				ok=1,pre[to[i]]=i,now[k]=i,k=to[i];
				break;
			}
		}
		if(!ok)
		{
			if(--gap[dep[k]]==0)break;
			int mindep=n+10;
			for(int i=head[k];i;i=nex[i])if(dep[to[i]]<mindep&&v[i])mindep=dep[to[i]];
			dep[k]=mindep+1,++gap[dep[k]],now[k]=head[k];
			if(k!=1)k=from[pre[k]];
		}
	}
	cout<<flow;
	return 0;
}