#include <fstream.h>
#define N 1001
#define INF 1<<30
ifstream in("maxflow.in");
ofstream out("maxflow.out");

int n,m,c[N][N],f[N][N],flux,coada[N],t[N],d[N];

void citire(){
     int x,y,cost;
     in>>n>>m;
     while(in>>x>>y>>cost) c[x][y] = cost;
}
int bfs(){
    int prim, ultim, i;

    for(i=1;i<=n;++i) coada[i] = t[i] = d[i] = 0;

    prim = ultim = 1;

    coada[prim] = 1;
    d[1] = INF;

    while(prim<=ultim){
	 for(i=1;i<=n;++i)
	    if(t[i] == 0 && c[coada[prim]][i]-f[coada[prim]][i]>0){
	      coada[++ultim] = i;
	      t[i] = coada[prim];
	      if(d[coada[prim]] < c[coada[prim]][i] - f[coada[prim]][i])
		 d[i] = d[coada[prim]];
	      else d[i] = c[coada[prim]][i] - f[coada[prim]][i];
	      if(i==n) return d[n];
	    }
	 prim++;
    }
    return 0;
}
void maxflow(){
     int min,i,j;
     do{

       min = bfs();
       if(min>0){
	 flux += min;
	 i=n;
	 while(i!=1){
	      j = t[i];
	      f[j][i] += min;
	      f[i][j] -= min;
	      i=j;
	 }
       }
     }while(min!=0);
}

int main(){
    citire();
    maxflow();
    out<<flux;
    return 0;
}