#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int N,M,sol,ap[1010];
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;
	//cout<<"Minimul in "<<nod<<" este "<<mn<<'\n';
	
	
	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+=sum;
					a[it->first][nod].flux+=sum;
				}
				else
				{
					a[nod][it->first].flux-=sum;
					a[it->first][nod].flux-=sum;
				}
				sum+=val;
			}
			
			//cout<<"Minimul in "<<nod<<" este "<<mn<<'\n';
			//cout<<"a[2][4]="<<a[2][4].flux<<'\n';
			//cout<<"Sum in "<<nod<<" este "<<sum<<'\n';
			
			ap[it->first]=0;
		}
	}
	
	return sum;
}


int main()
{
	ifstream in("maxflow.in");
	ofstream out("maxflow.out");
	
	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;
	}
	
	ap[1]=1;
	DFs(1,2000000000);
	
	cout<<'\n';
	/*for(int i=1;i<=N;++i)
	{
		for(int j=1;j<=N;++j)
		{
			cout<<a[i][j].flux<<' ';
		}
		cout<<'\n';
	}
	cout<<'\n';*/
	
	out<<sol<<'\n';
	out.close();
	return 0;
}