#include<stdio.h>
#define infile "maxflow.in"
#define outfile "maxflow.out"
#define nmax 1001
#define mmax 5001
#define inf ~(1<<31)
int st=1,fi;
struct mat
	{
	int f,c; //fluxul si capacitatea
	} fc[nmax][nmax]; //matricea in care vom retine fluxul si capacitaea intre doua muchii
struct lista
	{
	int n,p; //nodul si pozitia
	} l[mmax],lt[mmax]; //lista normala...si lista grafului transpus
char viz[nmax]; //ca sa stim daca am mai vizitat nodul in parcurgerea respectiva sau nu
char b[nmax]; //aici marcam nodurile blocate (pe care sa nu le mai apelam...pt k le apelam degeaba...nu vor mai aduce imbunatatiri ;))
int p[nmax],pt[nmax]; //pozitiile din lsita a fiilor pt graful normal si pt graful transpus
int n; //numarul de noduri
int flux; //fluxul maxim al retelei de transport

int minim(int a, int b)
	{
	if(a<b) return a;
	return b;
	}

//adauga in lista grafului arcul (x,y)
void add(struct lista l[mmax], int p[nmax], int m, int x, int y)
	{
	l[m].n=y; l[m].p=p[x]; p[x]=m;
	}

void citire()
	{
	int i,m,x,y,z;
	scanf("%d %d\n",&n,&m); //citim numarul de noduri si numarul de muchii
	fi=n; //punctul de iesire din graf
	for(i=1;i<=m;i++)
		{
		scanf("%d %d %d\n",&x,&y,&z);
		fc[x][y].c=z; //capacitatea arcului (x,y)
		add(l,p,i,x,y); //graful normal
		add(lt,pt,i,y,x); //graful transpus
		}
	}

//parcurgerea in adancime pentru determinarea fluxului maxim
int dfs(int x, int f) //se poate ajunge la nodul x cu fluxul f
	{
	viz[x]=1; //marcam k l-am atins
	if(x==fi) { flux+=f; return 0; } //am ajuns la iesire...adaug la fluxul total...si returnez 0 (am folosit tot fluxul)
	int ul,y,c,cr;
	for(ul=p[x];ul&&f;ul=l[ul].p) //trecem pe la fiecare copil al lui x (in graful normal)
		if(!viz[l[ul].n]&&!b[l[ul].n]&&(fc[x][l[ul].n].c-fc[x][l[ul].n].f)>0) //daca nodul nu este deja vizitat in aceasta parcurgere, si daca acest arc nu este saturat
			{
			y=l[ul].n; //salvam nodul
			c=minim(f,fc[x][y].c-fc[x][y].f); //fluxul maxim cu care putem apela acest nod
			cr=dfs(y,c); //apelam nodul y, cu fluxul c
			viz[y]=0; //cand am apelat functia dfs, s-a vizitat nodul...acum il marcam ca nevizitat;))
			if(cr&&y!=fi) b[y]=1; //s-a intors cu cost...acest nod nu va mai fi apelat
			fc[x][y].f+=(c-cr); //adaugam la fluxul acestui arc, fluxul folosit de nod
			f-=(c-cr); //scad din fluxul total fluxul folosi;))
			}
	//incercam parcurgerile in sens invers (destinatie-sursa)
	for(ul=pt[x];ul&&f;ul=lt[ul].p) //trecem pe la fiecare copil al lui x in graful transpus
		if(!viz[lt[ul].n]&&!b[lt[ul].n]&&fc[lt[ul].n][x].f) //daca nodul nu este deja viziat in parcurgerea asta, si daca avem flux;))
			{
			y=lt[ul].n; //salvam nodul
			c=minim(f,fc[y][x].f); //fluxul maxim cu care putem inainta ;))
			cr=dfs(y,c); //apelam nodul y cu fluxul c(este nod destinatie - sursa)
			//if(cr&&y!=fi) b[y]=1; //s-a intors cu cost....acest nod nu va mai fi apelat
			viz[y]=0; //scaotem vizitarea
			fc[y][x].f-=(c-cr); //fiinda am parcurs arcul in sens invers....voi scade fluxul folosit din cel total
			f-=(c-cr); //scadem din fluxul total pe cel folosit
			}
	return f; //returnam fluxul ramas
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(); //citim datele din fisier...si salvam graful normal si graful transpus in memorie
dfs(st,inf); //parcurgem din nodul de start....cu capacitate infinita
printf("%d",flux); //afisem fluxul maxim al retelei

fclose(stdin);
fclose(stdout);
return 0;
}