#include <stdio.h>
#include <vector>
using namespace std;
#define FI fopen("maxflow.in","r")
#define FO fopen("maxflow.out","w")

long mat[1001][1001];
int n;
long sol;
int viz[1001],vizRun;

void citeste(FILE *f) {
	int m,i,a,b;
	long c;
	fscanf(f,"%i%i",&n,&m);
	for(i=0;i<m;i++) {
		fscanf(f,"%i%i%li",&a,&b,&c);
		if(a==1 && b==n)
			sol+=c;
		else
			mat[a][b]=c;
	}
}

long min(long a,long b) { if(a<b) return a; return b; }
long gasesteDrum(int st[],int niv,long val) {
	int i;
	long aux;
	if(st[niv-1]==n)
		return val;
	for(i=1;i<=n;i++)
		if(viz[i]==0)
			if(mat[st[niv-1]][i]) {
				viz[i]=1;
				st[niv]=i;
				aux=gasesteDrum(st,niv+1,min(val,mat[st[niv-1]][i]));
				viz[i]=0;
				if(aux) {
					mat[st[niv-1]][i]-=aux;
					mat[i][st[niv-1]]+=aux;
					return aux;
				}
			}
	return 0;
}

void flux() {
	int st[1001];
	long aux;
	st[0]=1;
	viz[1]=1;
	while((aux=gasesteDrum(st,1,0x7fffffff)))
		sol+=aux;
}

int main() {
	citeste(FI);
	flux();
	fprintf(FO,"%li",sol);
	return 0;
}