#include <stdio.h>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

#define MAX_N 1001
#define NIL -1
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))

struct Arc {
  int f; // extremitatea finala a arcului
  int c;
  int ii; // indicele pentru arcul invers
};

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int c[MAX_N][MAX_N]; // matrice de adiacență
int e[MAX_N];        // excesul
int h[MAX_N];        // înălțimea
int hc[2 * MAX_N];   // hc[i] = numărul de noduri de înălțime i
int urm[MAX_N], ant[MAX_N]; // sortare topologică a rețelei admisibile
int head;            // începutul listei urm-ant
int n, m;
vector<Arc> a[MAX_N];
unsigned int sau[MAX_N]; // vector care arata urmatorul arc din vectorul de arce al unui nod

void initPreflow() {
  vector<Arc>::iterator it;
  int vol, vecin;

  h[1] = n;
  hc[0] = n - 1;
  hc[n] = 1;
  for (unsigned int i = 0; i < a[1].size(); i++) {
    vol = a[1][i].c;
    vecin = a[1][i].f;
    e[vecin] = vol;
    a[1][i].c = 0;
    a[vecin][a[1][i].ii].c = vol;
  }
  for (int i = 2; i < n - 1; i++) {
    urm[i] = i + 1;
    ant[i + 1] = i;
  }
  ant[2] = NIL;
  urm[n - 1] = NIL;
  head = 2;
}

void push (int u) {
  Arc arc = a[u][sau[u]];

  if (arc.c != 0) {
    int vol = MIN(e[u], arc.c);
    e[u] -= vol;
    e[arc.f] += vol;
    a[u][sau[u]].c -= vol;
    a[arc.f][arc.ii].c += vol;
    //cout << u << ' ' << e[u] << ' ' << arc.f << ' ' << e[arc.f] << '\n';
  }
}

void relabel (int u) {
  int oldh = h[u];

  hc[h[u]]--;
  h[u] = 2 * n; // înălțimile nu vor depăși 2n - 1
  for (unsigned int i = 0; i < a[u].size(); i++)
    if (a[u][i].c > 0)
      h[u] = MIN(h[u], 1 + h[a[u][i].f]);
  hc[h[u]]++;
  // gap heuristic
  /*
  if (!hc[oldh]) {
    for (int v = 0; v < n; v++) {
      if (h[v] > oldh) {
        h[v] = MAX(h[v], n + 1);
      }
    }
  }
  */
}

void discharge (int u) {
  Arc au; // arcul urmator

  while (e[u]) {
    au = a[u][sau[u]]; // vecinul urmator
    if (h[u] == h[au.f] + 1 and au.c > 0) {
      push(u);
    }
    sau[u]++;
    if (sau[u] == a[u].size()) {
      sau[u] = 0;
      relabel(u);
    }
  }
}

int main() {
  int i, j, c, i1, i2;
  Arc arc;

  fin >> n >> m;
  for (int im = 1; im <= m; im++) {
    fin >> i >> j >> c;
    arc.f = j; arc.c = c;
    a[i].push_back(arc);
    i1 = a[i].size() - 1;
    arc.f = i; arc.c = 0;
    a[j].push_back(arc);
    i2 = a[j].size() - 1;
    a[i][i1].ii = i2; a[j][i2].ii = i1;
  }
  initPreflow();
  int u = head;
  while (u != NIL) {
    if (e[u]) {
      relabel(u);
      discharge(u);
      if (ant[u] != NIL) { // altfel u este deja primul
        urm[ant[u]] = urm[u];
        if (urm[u] != NIL) {
          ant[urm[u]] = ant[u];
        }
        urm[u] = head;
        ant[u] = NIL;
        ant[head] = u;
        head = u;
      }
    }
    u = urm[u];
  }
  fout << e[n];
  return 0;
}