#include<fstream>
#include<cmath>
using namespace std;
int n,m,s,d; // s=nodul sursa | d=nodul destinatie
int C[1010][1010]; // capacitatea fiecarui arc
int F[1010][1010]; // fluxul fiecarui arc
int vizitat[1010]; // in acest vector vom marca nodurile
int Q[1010],inc,sf; //coada folosita in parcurgerea BFS

void Citire()
{
	int i,x,y,c;
	ifstream fin("maxflow.in");
	fin>>n>>m;
	s=1;
	d=n;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		C[x][y]=c;
	}
	fin.close();
}

int BFS()
{
	//returneaza 1 daca nodul destinatie nu a fost marcat
	int i,x;
	Q[0]=s;
	inc=sf=0;
	vizitat[s]=1;
	while(sf<=inc && vizitat[d]==0)
	{
		x=Q[sf];
		sf++;
		for(i=1;i<=n;i++)
		{
			if(vizitat[i]==0)
			{
				if(F[x][i]<C[x][i])
				{
					vizitat[i]=x;
					Q[++inc]=i;
				}
				else
					if(F[i][x]>0)
					{
						vizitat[i]=-x;
						Q[++inc]=i;
					}
			}
		}
	}
	if(vizitat[d]==0)
		return 1;
	return 0;
}

void Edmonds_Karp()
{
	int i,a,b,lg,v;
	int L[1000]; // L = lant de ameliorare a fluxului
	do
	{
		//marcam nodurile printr-o parcurgere BFS
		memset(vizitat,0,sizeof(vizitat));
		if(BFS()==1) //daca nodul destinatie nu a fost marcat am gasit fluxul maxim
			return;
		L[0]=d;
		lg=0;
		a=b=2000000000;
		while(L[lg]!=s)
		{
			lg++;
			L[lg]=abs(vizitat[L[lg-1]]);
			if(vizitat[L[lg-1]]>0)
				a=min(a,C[L[lg]][L[lg-1]]-F[L[lg]][L[lg-1]]);
			else
				if(vizitat[L[lg-1]]<0)
					b=min(b,F[L[lg-1]][L[lg]]);
		}
		v=min(a,b);
		//marim fluxul de-a lungul lantului de ameliorare cu v
		for(i=lg;i>0;i--)
		{
			if(vizitat[L[i-1]]>0)
				F[L[i]][L[i-1]]+=v;
			else
				F[L[i]][L[i-1]]-=v;
		}
	}
	while(1);
}

void Afisare()
{
	ofstream fout("maxflow.out");
	int i,sol=0;
	for(i=1;i<=n;i++)
	{
		sol+=F[i][d]; 		//fluxul maxim este suma fluxurilor care intra in d
		/* sol+=F[s][i]; */ //sau suma fluxurilor care ies din s
	}
	fout<<sol<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Edmonds_Karp();
	Afisare();
	return 0;
}