#include<cstdio>
using namespace std;
#define nmax 1024
#define inf 0x3f3f3f3f
struct info{
	int c,g;
};
info a[nmax][nmax];//cap si flux pt arce
int t,v,n,i,m[nmax];//etichete varfuri
int x,y,ll,min1,min2,min0,d[nmax];

void cit(){
	int m,i,j,x,y,z;
	freopen("maxflow.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j){
			a[i][j].c=-1;
			a[i][j].g=0;
		}
	scanf("%d",&m);
	for(i=1;i<=m;++i){
		scanf("%d %d %d",&x,&y,&z);
		a[x][y].c=z;
	}
}
void eticheta(int k){
	int j;
	if(t==0)
		for(j=1;j<=n;++j)
			if(a[k][j].c>=0 && m[j]==0 && a[k][j].c!=a[k][j].g){
				m[j]=k;
				if(j==n) t=1;
				else eticheta(j);
			}
	        else
		      if(a[j][k].c>=0 && m[j]==0 && a[j][k].g!=0){
			    m[j]=-k;
			    eticheta(j);
		      }
}

void genlant(int k){
		int aux,p;
		aux=m[k];
		if(aux!=n+1){
			if(aux>0){
				if(min1>a[aux][k].c-a[aux][k].g)
					min1=a[aux][k].c-a[aux][k].g;
			}
			else
				if(min2>a[k][-aux].g)
						min2=a[k][-aux].g;
				p=aux; if(p<0) p=-p;
				genlant(p);
				ll++;
				d[ll]=k;
			}
			else{
				d[1]=1;
				ll=1;
			}
}
void marire(){//mareste flux g foloind un lant nesat memorat in d

	min1=min2=inf;
	genlant(n);
	if(min1<2) 
		min0=min1;
	else
		min0=min2;
	for(i=1;i<=ll-1;++i){
		x=d[i];
		y=d[i+1];
		if(m[y]>0)
			a[x][y].g=a[x][y].g+min0;
		else
			a[y][x].g=a[y][x].g-min0;
	}
	v=v+min0;
}
int main(){
	freopen("maxflow.out","w",stdout);
	cit();
	do{
		for(int j=1;j<=n;++j) m[j]=0;
		m[1]=n+1;
		t=0;
		eticheta(1);
		if(m[n]!=0) marire();
	}while(m[n]!=0);
	printf("%d\n",v);
	return 0;
}