#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
int viz[nmax]; //ca sa stim daca am mai vizitat nodul in parcurgerea respectiva sau nu, si sa salvam tatal cu care l-am parcurs :P
int p[nmax],pt[nmax]; //pozitiile din lsita a fiilor pt graful normal si pt graful transpus
int n; //numarul de noduri

inline int modul(int x)
	{
	if(x<0) return (-1)*x;
	return x;
	}

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

//adauga in lista grafului arcul (x,y)
inline 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
		}
	}

//parcurgem reteaua...in oricare sens
int bfs()
	{
	int ul;
	int c[nmax],cs,cd; //coada
	c[cs=cd=1]=st; viz[st]=1; //initializam coada
	while(cs<=cd) //cat timp am elemente in coada
		{
		for(ul=p[c[cs]];ul;ul=l[ul].p) //ii luam toti copii de pe graful normal (sursa-destinatie)
			if(!viz[l[ul].n]&&fc[c[cs]][l[ul].n].f<fc[c[cs]][l[ul].n].c) //daca nodul nu a fost vizitat, si daca arcul nu este satura
				{
				viz[l[ul].n]=c[cs]; //salvam tatal cu care l-am atins
				c[++cd]=l[ul].n; //il adaugam in coada ;))
				if(l[ul].n==fi) return 1; //s-a atins nodul final
				}
		for(ul=pt[c[cs]];ul;ul=lt[ul].p) //luam acum copii din graful transpus (destinatie-sursa)
			if(!viz[lt[ul].n]&&fc[lt[ul].n][c[cs]].f) //daca nodul nu a mai fost vizitat, si daca avem flux pe acest arc
				{
				viz[lt[ul].n]=-c[cs]; //salvam tatal cu care l-am atins (insa cu sens negativ, ca sa stim ca e in graful transpus)
				c[++cd]=lt[ul].n; //il adaugam in coada
				if(lt[ul].n==fi) return 1; // inseamna k s-a atins nodul final
				}
		cs++; //inaintam in coada :P
		}
	return 0; //daca s-a ajuns aici, inseamna k nu s-a atins finalul
	}

//determina fluxul maxim din retea
int determina_flux()
	{
	int flux=0; //aici calculam fluxul retelei de transport
	int i,val;
	int s[nmax]; //stiva in care vom reface lantul ;))
	while(bfs()) //cat timp se atinge nodul final....deci putem face lanturi de ameliorare
		{
		val=inf; //variabila in care calculam valoarea lantului de ameliorare
		s[s[0]=1]=fi; //punem in stiva nodul final
		while(s[s[0]]!=st) //cat timp nu am adaugat tot lantul in stiva
			{
			s[++s[0]]=modul(viz[s[s[0]-1]]); //adaugam nodul cu care am vizitat ultimul nod adaugat in stiva
			if(viz[s[s[0]-1]]>0) //avem arc normal
				val=minim(val,fc[s[s[0]]][s[s[0]-1]].c-fc[s[s[0]]][s[s[0]-1]].f); //salvam minimul dintre fluxul curent...si fluxul arcului
			else //avem arc invers (destinatie-sursa)
				val=minim(val,fc[s[s[0]-1]][s[s[0]]].f); //salvam minimul dintre fluxul curent si fluxul arcului
			}
		flux+=val; //adaugam la fluxul curent fluxul obtinut de acest lant
		while(s[0]>1) //cat timp avem de refacut fluxul pe lant
			{
			if(viz[s[s[0]-1]]>0) //daca am parcurs arcul (s[s[0]],s[s[0]-1]) in sens normal
				fc[s[s[0]]][s[s[0]-1]].f+=val; //adaug la fluxul arcului fluxul folosit
			else //inseamna k arcul a fost parcurs in sens invers
				fc[s[s[0]-1]][s[s[0]]].f-=val; //acum scadem fluxul folosit ;))
			s[0]--; //trecem la copil:P
			}
		for(i=1;i<=n;i++) viz[i]=0; //golim vectorul viz
		}
	return flux; //returnam valoarea fluxului retelei ;))
	}

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

citire(); //citim datele din fisier...si salvam graful normal si graful transpus in memorie
printf("%d",determina_flux()); //calculam si afisem fluxul maxim al retelei

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