#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 int getmin(int a,int b,int sens)
{
	if(!a) return 2000000000;
	if(sens>0)
	{
		return cap[a][b]-flux[a][b];
	}
	return cap[a][b];
}

inline bool CHECK()
{
	for(int i=0;i<=N;++i) tata[i]=cd[i]=0;
	cd[1]=1;
	tata[1]=0;
	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(getmin(nod,it->first,it->second)>0 && !tata[it->first])
			{
				Q.push(it->first);
				tata[it->first]=nod;
				cd[it->first]=it->second;
			}
		}
	}
	
	if(tata[N]) return true;
	return false;
}

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)
		{
			if(tata[it->first])
			{
				int mflow=getmin(it->first,N,cd[it->first]);
			
				cout<<"TATA: ";
				for(int i=1;i<=N;++i) cout<<tata[i]<<' ';
				cout<<'\n';
				cout<<"CD: ";
				for(int i=1;i<=N;++i) cout<<cd[i]<<' ';
				cout<<'\n';
				cout<<N<<' ';
				for(int i=it->first;i>0;i=tata[i])
				{
					cout<<i<<' ';
					mflow=min(mflow,getmin(tata[i],i,cd[tata[i]]));
				}
				cout<<" cu mflow="<<mflow<<'\n';
				flux[it->first][N]+=mflow*(cd[N]);
				cout<<flux[it->first][N]<<' ';
				for(int i=it->first;i>0;i=tata[i])
				{
					flux[tata[i]][i]+=mflow*(cd[i]);
					cout<<flux[tata[i]][i]<<' ';
				}
				cout<<"\n\n\n";
				flow+=mflow;
			}
		}
		cout<<"\nEND\n\n";
	}
	
	out<<flow<<'\n';
	out.close();
	return 0;
}