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

int N,M;
vector< pair<int,int> > A[1010];
int flux[1010][1010],cap[1010][1010],tata[1010],cd[1010];
queue<int> Q;

inline bool CHECK()
{
	for(int i=0;i<=N;++i) tata[i]=0;
	tata[1]=1;
	Q.push(1);
	for(;!Q.empty();Q.pop())
	{
		int nod=Q.front();
		for(vector< pair<int,int> >::iterator it=A[nod].begin();it!=A[nod].end();++it)
		{
			if(flux[nod][it->first]<cap[nod][it->first] && !tata[it->first])
			{
				Q.push(it->first);
				tata[it->first]=nod;
				cd[it->first]=it->second;
			}
		}
	}
	
	if(tata[N]) return true;
	return false;
}

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

int main()
{
	ifstream in("maxflow.in");
	ofstream out("maxflow.out");
	
	in>>N>>M;
	for(int i=1;i<=M;++i)
	{
		int x,y,cost;
		in>>x>>y>>cost;
		cap[x][y]=cost;
		A[x].push_back(make_pair(y,+1));
		A[y].push_back(make_pair(x,-1));
	}
	
	int flow=0;
	for(;CHECK();)
	{
		for(vector< pair<int,int> >::iterator it=A[N].begin();it!=A[N].end();++it)
		{
			int mflow=getmin(it->first,N,cd[it->first]);
			
			for(int i=it->first;i>1;i=tata[i])
			{
				mflow=min(mflow,getmin(tata[i],i,cd[tata[i]]));
			}
			flux[it->first][N]+=mflow*(cd[N]);
			for(int i=it->first;i>1;i=tata[i])
			{
				flux[tata[i]][i]+=mflow*(cd[i]);
			}
			flow+=mflow;
		}
	}
	
	out<<flow<<'\n';
	out.close();
	return 0;
}