#include <stdio.h>

#define Nmax 101

int n,m,s,t;
long FLUX;
int c[Nmax][Nmax], f[Nmax][Nmax];
int d[Nmax], sor[Nmax*Nmax];
int os[Nmax];


void Olvas()
{
	int a,b;
	long x;
	int i;

	freopen("maxflow.in", "r", stdin);
	scanf("%d %d", &n, &m);

	for (i=1;i<=m;i++)
	{
		scanf("%d %d %ld", &a, &b, &x);
		c[a][b] = x;
		f[a][b] = x;
	}


	s = 1;
	t = n;
}


void Desit()
{
	int e,v,u,i;
	e = v = 1;
	sor[1] = t;

	while (e<=v)
	{
		u = sor[e];
		for (i=1;i<=n;i++)
		{
			if (c[i][u] && (d[i]>d[u]+1 || d[i]==0))
			{
				d[i] = d[u] + 1;
				sor[++v] = i;
			}
		}
		++e;
	}
}



int Minkeres(int x)
{
	int i=1;

	while (!(f[x][i] && d[i] == d[x]-1 && (d[i]!=0 || i==t)) && i<=n)
	{
		i++;
	}
	return (i<=n)?i:0;
}


void Lep(int *x, int y, int *minut)
{
	if (f[*x][y] < *minut)
		*minut = f[*x][y];
	os[y] = *x;
	*x = y;
}


void Modosit(int er)
{
	int x;

	x = t;
	while (x != s)
	{
		f[os[x]][x] -= er;
		f[x][os[x]] += er;
		x = os[x];
	}
}

void Vissza(int *csucs)
{
	int min = 0, i;

	for (i=1;i<=n;i++)
	{
		if (f[*csucs][i] && (d[i]+1 < min || min==0) && (d[i] || i==t))
		{
			min = d[i] + 1;
		}
	}

	d[*csucs] = min;
	if (*csucs != s) *csucs = os[*csucs];
}



long Szamol()
{
	int ss = 0, i;

	for (i=1;i<=n;i++)
		ss += f[i][s];
	return ss;
}


void Megold()
{
	int x = s, minut, y;
	Desit();

	while (d[s])
	{
		if (x==s) minut = 30000;
		if ((y = Minkeres(x))>0)
		{
			Lep(&x, y, &minut);
			if (x == t)
			{
				Modosit(minut);
				x = s;
			}


		}
		else Vissza(&x);
	}
	FLUX = Szamol();
}



void Kiir()
{
	freopen("maxflow.out","w",stdout);
	printf("%ld", FLUX);
}








int main()
{
	Olvas();
	Megold();
	Kiir();
	return 0;
}