#include <cstdio>
#define DIM 1005

int n, m, c[DIM][DIM], T[DIM], fluxmaxim, QQ, v[DIM], nr;
struct nod
{
	int x;
	nod *next;
};

void afisare()
{
	for (int i = 1; i <= n; ++i)
	{
		printf("%d:", i);
		for (int j = 1; j <= n; ++j)
			printf ("%3d ", c[i][j]);
		printf("\n");
		
	}
}

int BFS()
{
	nod *st = new nod, *dr, *t;
	st -> x = 1;
	st -> next = NULL;
	dr = st;
	int i, k;
	for (i = 1; i <= n; ++i)
		T[i] = -1;
	T[1]=0;
	while (st)
	{
		k = st -> x;

		for (i = 1; i <= n; ++i)
			if (c[k][i] && T[i] == -1)
			{
					t = new nod;
					t -> x = i;
					t -> next = NULL;
					dr -> next = t;
					dr = t;
					
					T[i] = k;
					
			}
		t = st -> next;
		delete st;
		st = t;
	}
	
	return 1;
	
}

void EK(){
	int gata = 0;
	while(!gata){
		BFS();
		gata = 1;
		
		for (int j = 1; j <= nr; ++j)
			if (c[v[j]][n] > 0 && T[v[j]] != -1)
			{
				T[n] = T[j];
				
				int i=n, cmin=1<<30;
				int * t=T;
				for(i=n ; t[i]; i=t[i])
					if(c[t[i]][i]<cmin)
						cmin=c[t[i]][i];
				if (cmin != (1<<30))
				{
					gata = 0;
				fluxmaxim+= cmin;
				for(i=n ; t[i]; i=t[i]){
					c[t[i]][i] -= cmin;
					c[i][t[i]] += cmin;
				}
				}
			}
	}
}

int main()
{
	FILE *f = fopen("maxflow.in", "r");
	
	fscanf(f, "%d%d", &n, &m);
	for (int i = 1, x, y, cc; i <= m; ++i)
	{
		fscanf(f, "%d%d%d", &x, &y, &cc), c[x][y]=cc;
		if (y == n)
			v[++nr] = x;
	}
	fclose(f);
//	afisare();
	EK();
	f = fopen("maxflow.out", "w");
	
	fprintf(f, "%d\n", fluxmaxim);
	fclose(f);
	return 0;
}