#include <cstdlib>
#include <iostream>
#include <fstream>
#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];

ifstream in("maxflow.in");
ofstream out("maxflow.out");

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(nrr<1000001)
	{
		++nrr;
		//cout<<nod<<' '<<mn<<'\n';
	}
	else
	{
		out<<nod<<' '<<mn;
		exit(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 a1=min(nod,it->first),a2=max(nod,it->first);
				int val=DFs(it->first,max(0,min(getmin(nod,it->first,it->second),mn-sum)));
				if(it->second>0)
				{
					a[a1][a2].flux+=val;
				}
				else
				{
					a[a2][a1].flux-=val;
				}
				sum+=val;
			}
			
			ap[it->first]=0;
		}
	}
	
	return sum;
}


int main()
{	
	in>>N>>M;
	for(int i=1;i<=M;++i)
	{
		int x1,x2,cost;
		in>>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);
	
	out<<sol<<'\n';
	out.close();
	return 0;
}