#include <stdio.h>

#define MAX_N 1000
#define MAX_M 5000
#define NIL -1
#define INFTY 1000000
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))

typedef struct {
  short v;
  int c, next;
} cell;

cell l[2 * MAX_M];
int adj[MAX_N];
int q[MAX_N], qstart, qend; // coada BFS
int p[MAX_N];               // vectorul de părinți
int e[MAX_N];               // e[i] = pointer la muchia p[i]->i
int m, n;

void addChild(int u, int v, int c, int pos) {
  l[pos].v = v;
  l[pos].c = c;
  l[pos].next = adj[u];
  adj[u] = pos;
}

// Caută un drum de creștere de lungime minimă (ca număr de muchii)
int bfs(int s, int t) {
  q[0] = s;
  qstart = 0;
  qend = 1;

  for (int u = 0; u < n; u++) {
    p[u] = NIL;
  }

  while ((qstart != qend) && (p[t] == NIL)) {
    int u = q[qstart];
    for (int pos = adj[u]; pos != NIL; pos = l[pos].next) {
      int v = l[pos].v;
      // Consideră doar muchiile prin care mai pot pompa flux spre noduri
      // încă neexplorate
      if ((p[v] == NIL) && l[pos].c) {
        p[v] = u;
        e[v] = pos;
        q[qend++] = v;
      }
    }
    qstart++;
  }

  int newFlow = 0;

  // Iterează prin predecesorii lui t (care sunt și succesori datorită
  // rețelei reziduale)
  for (int pos = adj[t]; pos != NIL; pos = l[pos].next) {
    int v = l[pos].v;
    int other = pos ^ 1;
    if (l[other].c && p[v] != NIL) { // TODO dar dacă avem o muchie s->t?
      p[t] = v;
      e[t] = other; // Ca să includem muchia v->t în lanț
      
      // Află minimul de pe cale
      int min = INFTY;
      v = t;
      while (v != s) {
        min = MIN(min, l[e[v]].c);
        v = p[v];
      }

      // Pompează acel minim
      v = t;
      while (v != s) {
        l[e[v]].c -= min;
        l[e[v] ^ 1].c += min; // Muchia inversă
        v = p[v];
      }
      newFlow += min;
    }
  }

  return newFlow;
}

int main(void) {
  int u, v, c;
  FILE *f = fopen("maxflow.in", "r");
  fscanf(f, "%d%d", &n, &m);
  for (u = 0; u < n; u++) {
    adj[u] = NIL;
  }
  for (int i = 0; i < m; i++) {
    fscanf(f, "%d%d%d", &u, &v, &c);
    addChild(u - 1, v - 1, c, 2 * i);
    addChild(v - 1, u - 1, 0, 2 * i + 1);
  }
  fclose(f);

  int flow = 0, augment;
  do {
    augment = bfs(0, n - 1);
    flow += augment;
  } while (augment);

  f = fopen("maxflow.out", "w");
  fprintf(f, "%d\n", flow);
  fclose(f);
}