#include <bits/stdc++.h>
using namespace std;

struct stopwatch {
  clock_t t = clock();
  void restart() { t = clock(); }
  int elapsed() const { return (clock() - t) * 1000 / CLOCKS_PER_SEC; }
  friend string to_string(stopwatch sw) {
    return "Time: " + to_string(sw.elapsed()) + " ms";
  }
} sw;

int pushes, relabels;

template <class T> struct hlpp {
  struct edge {
    int to, rev;
    T f;
  };
  static constexpr T inf = numeric_limits<T>::max();
  const int n;
  vector<vector<edge>> g;
  vector<vector<int>> lst, gap;
  vector<T> excess;
  int highest = 0, work;
  vector<int> h, cnt, ptr;
  hlpp(int _n) : n(_n), g(n), lst(n + 1), gap(n), excess(n), h(n), cnt(n + 1), ptr(n) {}
  void add(int from, int to, T cap, bool directed = true) {
    g[from].push_back({to, (int)g[to].size(), cap});
    g[to].push_back({from, (int)g[from].size() - 1, directed ? 0 : cap});
  }
  void update_height(int v, int nh) {
    ++relabels;
    ++work;
    if (h[v] < n) --cnt[h[v]];
    h[v] = nh;
    if (nh == n) return;
    ++cnt[nh], highest = nh;
    gap[nh].push_back(v);
    if (excess[v] > 0) lst[nh].push_back(v);
  }
  void global_relabel(int t) {
    work = 0;
    fill(begin(h), end(h), n);
    fill(begin(cnt), end(cnt), 0);
    for (int i = 0; i < highest; ++i) lst[i].clear(), gap[i].clear();
    h[t] = 0;
    queue<int> que({t});
    while (not que.empty()) {
      int v = que.front();
      que.pop();
      for (auto&& e : g[v]) if (h[e.to] == n and g[e.to][e.rev].f > 0)
        que.push(e.to), update_height(e.to, h[v] + 1);
      highest = h[v];
    }
  }
  void push(int v, edge& e) {
    ++pushes;
    if (excess[e.to] == 0) lst[h[e.to]].push_back(e.to);
    T df = min(excess[v], e.f);
    e.f -= df, g[e.to][e.rev].f += df;
    excess[v] -= df, excess[e.to] += df;
  }
  void discharge(int v) {
    int nh = n;
    int sz = g[v].size();
    for (ptr[v] = 0; ptr[v] < sz; ++ptr[v]) {
    // for (int i = 0, sz = g[v].size(); i < sz; ++i) {
      edge &e = g[v][ptr[v]];
      if (e.f > 0) {
        if (h[v] == h[e.to] + 1) {
          push(v, e);
          if (excess[v] <= 0) return;
        } else nh = min(nh, h[e.to] + 1);
      }
    }
    if (cnt[h[v]] > 1) update_height(v, nh);
    else for (int i = h[v]; i <= highest; ++i) {
      for (int j : gap[i]) update_height(j, n);
      gap[i].clear();
    }
  }
  T max_flow(int s, int t) {
    fill(begin(excess), end(excess), 0);
    excess[s] = inf, excess[t] = -inf;
    global_relabel(t);
    for (auto&& e : g[s]) push(s, e);
    for (; highest >= 0; --highest) while (not lst[highest].empty()) {
      int v = lst[highest].back();
      lst[highest].pop_back();
      discharge(v);
      if (work > 4 * n) global_relabel(t);
    }
    return excess[t] + inf;
  }
};

template <class T> struct push_relabel {
  struct arc {
    int to, rev;
    T cap;
  };
  static constexpr T inf = numeric_limits<T>::max();
  const int n;
  vector<vector<arc>> g;
  vector<T> ex;
  vector<int> d, ptr, cnt;
  vector<vector<int>> active;
  int highest = -1, gap, works;
  push_relabel(int _n) : n(_n), g(n), ex(n), d(n), ptr(n), cnt(n), active(n) {}
  void add(int from, int to, T cap, bool directed = true) {
    assert(cap >= 0);
    if (from == to or cap == 0) return;
    g[from].push_back({to, (int)g[to].size(), cap});
    g[to].push_back({from, (int)g[from].size() - 1, directed ? 0 : cap});
  }
  void push(int v, arc& a) {
    ++pushes;
    if (ex[a.to] == 0 and d[a.to] < gap)
      active[d[a.to]].push_back(a.to), highest = max(highest, d[a.to]);
    T delta = min(ex[v], a.cap);
    ex[v] -= delta, ex[a.to] += delta;
    a.cap -= delta, g[a.to][a.rev].cap += delta;
  }
  void relabel(int v) {
    ++relabels;
    int mn = 2 * n;
    for (auto&& a : g[v]) if (a.cap) mn = min(mn, d[a.to]);
    if (--cnt[d[v]] == 0) gap = d[v];
    d[v] = mn + 1, ++works;
    if (d[v] < n) if (cnt[d[v]]++ == 0) while (cnt[gap]) ++gap;
  }
  void discharge(int v) {
    int i = ptr[v];
    for (int sz = g[v].size(); ex[v] and d[v] < gap; ) {
      if (i == sz) relabel(v), i = 0;
      else {
        arc &a = g[v][i];
        if (a.cap and d[v] > d[a.to]) push(v, a);
        else ++i;
      }
    }
    ptr[v] = i;
    // int sz = g[v].size();
    // while (ex[v] and d[v] < gap)
    //   if (ptr[v] == sz) relabel(v), ptr[v] = 0;
    //   else {
    //     arc &a = g[v][ptr[v]];
    //     if (a.cap and d[v] > d[a.to]) push(v, a);
    //     else ++ptr[v];
    //   }
  }
  void global_relabel(int t) {
    fill(begin(d), end(d), n), fill(begin(cnt), end(cnt), 0);
    fill(begin(active), end(active), vector<int>());
    queue<int> que;
    d[t] = 0, que.push(t);
    while (not que.empty()) {
      int v = que.front();
      que.pop();
      ++cnt[d[v]];
      gap = d[v] + 1;
      for (auto&& a : g[v]) if (g[a.to][a.rev].cap and d[a.to] == n) {
        d[a.to] = d[v] + 1, que.push(a.to);
        if (ex[a.to]) active[highest = d[a.to]].push_back(a.to);
      }
    }
  }
  T max_flow(int s, int t) {
    ex[s] = inf, ex[t] = -inf;
    for (auto&& a : g[s]) push(s, a);
    global_relabel(t);
    for (; highest >= 0; --highest) while (not active[highest].empty()) {
      int v = active[highest].back();
      active[highest].pop_back();
      discharge(v);
      if (works > 4 * n) global_relabel(t), works = 0;
    }
    return inf + ex[t];
  }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  push_relabel<long long> g(n);
  // hlpp<long long> g(n);
  while (m--) {
    int u, v, c;
    cin >> u >> v >> c;
    // --u, --v;
    g.add(u, v, c);
  }
  cout << g.max_flow(0, n - 1) << '\n';
  // cerr << pushes << ' ' << relabels << '\n';
  // cerr << to_string(sw) << '\n';
}



Measured memory_bytes: 3268