#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;
	}
	while (1)
	{
		if (!bfs())
			break;
		int min=0x3f3f3f3f;
		for (int aa=n; aa!=1; aa=abs(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=abs(mrk[aa]))
		{
			f[abs(mrk[aa])][aa]+=min;
			f[aa][abs(mrk[aa])]-=min;
		}
	}
	long long sum=0;
	for (int i=1; i<=a[1][0]; i++)
		sum+=f[1][a[1][i]];
	fprintf(fout, "%lld\n",sum);
	fclose(fin);
	fclose(fout);
    return 0;
}