#include <iostream>
#include <vector>
#include <map>
#include <fstream>

using namespace std;

class Algorithm {
#define capacity second.second
#define preflow second.first
#define pair_preflow first
#define pair_capacity second
#define to first
  typedef vector<vector<pair<int, int > > > Graph;
  typedef vector<map<int, pair<int, int> > > FlowGraph;

  FlowGraph r;
  vector<int> count, label, x;
  vector<bool> active;
  vector<vector<int> > B;
  int b, n;

  void Enqueue (int nod) {
    if (x[nod] > 0 && !active[nod] && label[nod] < r.size ()) {
      B[label[nod]].push_back (nod);
      active[nod] = true;
      b = max (b, label[nod]);
    }
  }

  int Dequeue (int l) {
    int nod = B[l].back ();
    B[l].pop_back ();
    active[nod] = false;
    return nod;
  }

  void Push (int from, int to) {
    int d = max(0, min (x[from], r[from][to].pair_capacity - r[from][to].pair_preflow));
    if (label[from] == label[to] + 1 && d > 0) {
      x[from] -= d;
      x[to] += d;

      r[from][to].pair_preflow += d;
      r[to][from].pair_capacity -= d;
      Enqueue(to);
    }
  }

  void Relabel (int nod) {
    count[label[nod]]--;
    label[nod] = (int) r.size () - 1;
    for (auto it : r[nod]) {
      label[nod] = min (label[nod], label[it.to] + 1);
    }

    count[label[nod]]++;
    Enqueue(nod);
  }

  void Gap (int k) {
    for (int i = 1; i <= n; i++) {
      if (label[i] >= k) {
        count[label[i]]--;
        label[i] = max(label[i], (const int &) (r.size() - 1));
        count[label[i]]++;
        Enqueue(i);
      }
    }
  }

  void Discharge (int nod) {
    if (x[nod] > 0) {
      for (auto it : r[nod]) {
        Push (nod, it.to);
      }

      if (count[label[nod]] == 1) {
        Gap (label[nod]);
      }
      else {
        Relabel(nod);
      }
    }
  }

  int MaxFlow (Graph &g, int source, int dest) {
    r = FlowGraph (g.size ());
    active = vector<bool>(g.size ());
    x = vector<int>(g.size ());
    label = vector<int>(g.size ());
    count = vector<int>(g.size ());
    B = vector<vector<int> > (g.size ());
    b = 0;

    for (int i = 1; i < g.size (); i++) {
      for (auto it : g[i]) {
        r[i][it.to] = {0, it.pair_capacity};
      }
    }

    for (auto it : r[source]) {
      x[source] += it.capacity;
    }

    Enqueue (source);
    count[0] = (int) (g.size() - 1);
    active[dest] = true;

    while (b >= 0) {
      if (B[b].size () > 0) {
        int nod = Dequeue (b);
        Discharge(nod);
      }
      else {
        b--;
      }
    }

    active.clear ();
    label.clear ();
    count.clear ();
    int result = x[dest];
    x.clear ();
    return result;
  }
public:
  void run () {
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.in");
    int from, to, cap, n, m;
    cin >> n >> m;
    Graph g((unsigned long) (n + 1));
    for (int i = 0; i < m; i++) {
      cin >> from >> to >> cap;
      g[from].push_back ({to, cap});
    }

    cout << MaxFlow(g, 1, n);
  }
};

int main () {
  Algorithm algo;
  algo.run();
  return 0;
}