#include <cstdlib>
#include <cstdio>
#include <vector>
using namespace std;

int N,M,sol,ap[1010],nrr;
vector< pair<int,int> > A[1010];
struct matrix
{
	int flux,cap;
};
matrix a[1010][1010];

inline int getmin(int x1,int x2,int sens)
{
	if(sens>0)
	{
		return a[x1][x2].cap-a[x1][x2].flux;
	}
	return a[x1][x2].flux;
}

inline int DFs(int nod,int mn)
{
	int sum=0;
	if(nod==N)
	{
		sol=sol+mn;
		return mn;
	}
	
	for(vector< pair<int,int> >::iterator it=A[nod].begin();it!=A[nod].end();++it)
	{
		if(!ap[it->first])
		{
			ap[it->first]=1;
			if(nod==1) sum=0;
			if(max(0,min(getmin(nod,it->first,it->second),mn-sum)))
			{
				int val=DFs(it->first,max(0,min(getmin(nod,it->first,it->second),mn-sum)));
				if(it->second>0)
				{
					a[nod][it->first].flux+=val;
					a[it->first][nod].flux+=val;
				}
				else
				{
					a[nod][it->first].flux-=val;
					a[it->first][nod].flux-=val;
				}
				sum+=val;
			}
			
			ap[it->first]=0;
		}
	}
	
	return sum;
}


int main()
{	
	freopen("maxflow.in","r",stdin);
    freopen("maxflow.out","w",stdout);
    scanf("%d %d",&N,&M);
	for(int i=1;i<=M;++i)
	{
		int x1,x2,cost;
		scanf("%d %d %d",&x1,&x2,&cost);
		A[x1].push_back(make_pair(x2,+1));
		if(x1!=1 && x1!=N && x2!=1 && x2!=N) A[x2].push_back(make_pair(x1,-1));
		a[x1][x2].cap=cost;
		a[x2][x1].cap=cost;
	}
	ap[1]=1;
	DFs(1,2000000000);
	printf("%d\n",sol);
	return 0;
}