#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;
		cap[y][x]+=cost;
		A[x].push_back(make_pair(y,+1));
		if(x!=1 && x!=N && y!=1 && y!=N) 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])
				{
					if(cd[i]>0)
					{
						flux[tata[i]][i]+=mflow;
						flux[i][tata[i]]+=mflow;
					}
					else
					{
						flux[i][tata[i]]-=mflow;
						flux[tata[i]][i]-=mflow;
					}
					//cout<<flux[tata[i]][i]<<' ';
				}
				//cout<<"\n\n\n";
				flow+=mflow;
			}
		}
		//cout<<"\nEND\n\n";
	}
	
	out<<flow<<'\n';
	out.close();
	return 0;
}