#include <stdio.h>
#define MAXN 1000
#define MAXM 5000
#define INF 2000000000
int ult[MAXN], nod[2 * MAXM], next[2 * MAXM], cap[2 * MAXM], fol[2 * MAXM];
int q[MAXN], prev[MAXN], sp[MAXN];
char tr[MAXN];
int n;

inline int min2(int a, int b){
  return a < b ? a : b;
}

char bfs(){
  memset(tr, 0, sizeof tr);
  memset(prev, 0, sizeof prev);
  int a, k, poz, st = 0, dr = 1;
  q[0] = 0;
  tr[0] = 1;
  while(st < dr && !tr[n - 1]){
    a = q[st];
    st++;
    poz = ult[a];
    while(poz != -1){
      if(!tr[nod[poz]] && cap[poz] > fol[poz]){
        tr[nod[poz]] = 1;
        q[dr] = nod[poz];
        prev[nod[poz]] = a;
        sp[nod[poz]] = poz;
        dr++;
      }
      poz = next[poz];
    }
  }
  return tr[n - 1];
}

int main(){
  FILE *in = fopen("maxflow.in", "r");
  int m, i, x, y, z, dr = 0;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < n; i++)
    ult[i] = -1;
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d%d", &x, &y, &z);
    x--;  y--;
    nod[dr] = x;
    next[dr] = ult[y];
    ult[y] = dr;
    cap[dr] = 0;
    dr++;
    nod[dr] = y;
    next[dr] = ult[x];
    ult[x] = dr;
    cap[dr] = z;
    dr++;
  }
  fclose(in);
  int suma = 0, poz, p, augm;
  while(bfs()){
    poz = ult[n - 1];
    while(poz != -1){
      prev[n - 1] = nod[poz];
      sp[n - 1] = poz + 1;
      if(!(poz & 1) && tr[nod[poz]] && cap[poz + 1] > fol[poz + 1]){
        p = n - 1;
        augm = INF;
        while(p != 0){
          augm = min2(augm, cap[sp[p]] - fol[sp[p]]);
          p = prev[p];
        }
        p = n - 1;
        while(p != 0){
          fol[sp[p]] += augm;
          if(sp[p] & 1)
            fol[sp[p] - 1] -= augm;
          else
            fol[sp[p] + 1] += augm;
          p = prev[p];
        }
      }
      poz = next[poz];
    }
  }
  for(i = 0; i < n - 1; i++){
    poz = ult[i];
    while(poz != -1){
      if(nod[poz] == n - 1)
        suma += fol[poz];
      poz = next[poz];
    }
  }
  FILE *out = fopen("maxflow.out", "w");
  fprintf(out, "%d", suma);
  fclose(out);
  return 0;
}