#include <stdio.h>
#include <string.h>
#include <stdlib.h>

FILE *fin=fopen("maxflow.in","r");
FILE *fout=fopen("maxflow.out","w");

int a[2048][2048];
int c[2048][2048];
int f[2048][2048];
int mrk[2048];
int n,m;

bool bfs()
{
	int cd[2048];
	int st=0,en=0;
	memset(mrk,0,(n+1)*sizeof(int));
	mrk[1]=0x3f3f3f3f;
	cd[st]=1;
	while (st<=en)
	{
		for (int i=1; i<=a[cd[st]][0]; i++)
		{
			if (mrk[a[cd[st]][i]]) continue;
			int x=cd[st],y=a[cd[st]][i];
			if (f[x][y]<c[x][y])
			{
				mrk[y]=+x; cd[++en]=y;
			} //else 
				//if (f[y][x]>0)
				//{
				//	mrk[y]=-x; cd[++en]=y;
				//}
		}
		st++;
	}
	return mrk[n];
}

int main (int argc, char * const argv[]) {
    fscanf(fin, "%d %d",&n, &m);
	for (int i=0; i<n; i++)
		a[i][0]=0;
	for (int i=0; i<m; i++)
	{
		int x,y,cp;
		fscanf(fin, "%d %d %d",&x,&y,&cp);
		a[x][++a[x][0]]=y;
		a[y][++a[y][0]]=x;
		c[x][y]=cp;
		c[y][x]=f[x][y]=f[y][x]=0;
	}
	long long sum=0;
	while (1)
	{
		if (!bfs())
			break;
		int min=0x3f3f3f3f;
		for (int aa=n; aa!=1; aa=mrk[aa])
		{
			if (mrk[aa]>0)
			{
				if (c[mrk[aa]][aa]-f[mrk[aa]][aa]<min)
					min=c[mrk[aa]][aa]-f[mrk[aa]][aa];
			}
			//else
			//	if (f[-mrk[aa]][aa]>min)
			//		min=f[-mrk[aa]][aa];
		}
		for (int aa=n; aa!=1; aa=mrk[aa])
		{
			f[mrk[aa]][aa]+=min;
			f[aa][mrk[aa]]-=min;
		}
		sum+=min;
	}
	fprintf(fout, "%lld\n",sum);
	fclose(fin);
	fclose(fout);
    return 0;
}