#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
int d[nmax]; //d[i] - distanta nodului i fata de nodul final (distanta masurata in numarul de muchii)
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

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
		}
	}

//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]&&(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;))
			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]&&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)
			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
	}

//parcurgem graful transpus in latime pentru a afla distanta minima de la fiecare nod catre nodul final
void bfs(int x) //modul din care facem parcurgerea
	{
	int i,ul;
	int c[nmax],st,dr; //coada cu nodurile
	st=dr=1; c[st]=x; //initializam coada
	while(st<=dr) //cat timp avem elemente in coada
		{
		ul=pt[c[st]]; //pozitia din lista a lu fisu
		while(ul) //cat timp are copii
			{
			if(!d[lt[ul].n]) //daca nu a mai fost vizitat
				{
				c[++dr]=lt[ul].n; //il adaugam in coada
				d[lt[ul].n]=d[st]+1; //i salvam distanta;))
				}
			ul=lt[ul].p; //fratesu
			}
		st++; //inaintam in coada
		}
	}

inline void schimba(int *a, int *b)
	{
	int c=*a; *a=*b; *b=c;
	}

//sortam lista fiecareui nod din graful normal...dupa distanta fata de nodul final
void sortare(int ul) //pozitia din lista
	{
	int i,j;
	for(i=ul;i;i=l[i].p) //trecem pe la fiecare frate
		for(j=l[i].p;j;j=l[j].p) //trecem la toti fratii urmatori
			if(d[l[i].n]>d[l[i].n])
				{ //am gasit unul mai mic...va trebui sa le interschimbam ;))
				//schimba(&l[i].n,&l[j].n); //schimbam nodurile
				}
	}

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

citire(); //citim datele din fisier...si salvam graful normal si graful transpus in memorie
bfs(fi); //facem vectorul d[] pentru distante
int i; for(i=1;i<=n;i++) sortare(p[i]); //sortam
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;
}