#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
#define inf 0x3f3f3f3f
#define dim 1005
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
vector< pair <int,int> >v[dim];
int coada[dim*dim][3],n,m,sol;

void read()
{
	int i, x, y, t;
	fin>>n >>m;
	for(i=1;i<=m;++i)
	{
		fin>>x >>y >>t;
		v[x].pb(mp(y,t));
	}
}

void bfs()
{
	int inc=1, sf=1;
	coada[1][0]=1;
	
	while(inc<=sf)
	{
		int x=coada[inc][0];
		
		if(x==n)
		{
			int mic=inf,nod=inc;
			while(nod!=1)
			{
				int x0=coada[nod][1];
				int y0=coada[nod][0];
				int k;
				for(k=0;k<v[x0].size();++k)
					if(v[x0][k].fs==y0)
						break;
				
				mic=min(mic,v[x0][k].sc);
				nod=coada[nod][2];
			}
			
			nod=inc;
			
			while(nod!=1)
			{
				int x0=coada[nod][1];
				int y0=coada[nod][0];
				int k;
				for(k=0;k<v[x0].size();++k)
					if(v[x0][k].fs==y0)
					{
							v[x0][k].sc-=mic;
							break;
					}
				nod=coada[nod][2];
			}
			sol+=mic;
		}
		
		for(int k=0;k<v[x].size();++k)
		{
			coada[++sf][0]=v[x][k].fs;
			coada[sf][1]=x;
			coada[sf][2]=inc;
		}
		++inc;
	}
	
}

int main()
{
	read();
	bfs();
	fout<<sol;
	return 0;
}