#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

//
// Maximum flow (push-relabel)
//
// Complexity:
//     O(V^2 √E) time
//

template <typename T> class PushRelabel {
    struct edge {
        int to, rev, idx;
        T cap;
        bool isrev;
        edge(int to, T cap, int rev, bool isrev, int idx) :
            to(to), cap(cap), rev(rev), isrev(isrev), idx(idx) {}
    };

    void update_height(int idx, int next_height) {
        ++relabels;
        if (h[idx] != g.size() + 1) --cnt[h[idx]];
        h[idx] = next_height;
        if (h[idx] != g.size() + 1) {
            high = next_height;
            ++cnt[next_height];
            if (ex[idx] > 0) hs[next_height].emplace_back(idx);
        }
    }

    void global_relabel(int idx) {
        for (int i = 0; i <= high; ++i) hs[i].clear();
        relabels = high = 0;
        h.assign(g.size(), g.size() + 1);
        cnt.assign(g.size(), 0);
        queue<int> que;
        que.emplace(idx);
        h[idx] = 0;
        while (que.size()) {
            int p = que.front();
            que.pop();
            for (auto& e : g[p]) {
                if (h[e.to] == g.size() + 1 && g[e.to][e.rev].cap > 0) {
                    que.emplace(e.to);
                    high = h[p] + 1;
                    update_height(e.to, high);
                }
            }
        }
    }

    void push(int idx, edge& e) {
        if (h[e.to] == g.size() + 1) return;
        if (ex[e.to] == 0) hs[h[e.to]].emplace_back(e.to);
        T df = min(ex[idx], e.cap);
        e.cap -= df;
        g[e.to][e.rev].cap += df;
        ex[idx] -= df;
        ex[e.to] += df;
    }

    void discharge(int idx) {
        int next_height = g.size() + 1;
        for (auto& e : g[idx]) if (e.cap > 0) {
            if (h[idx] == h[e.to] + 1) {
                push(idx, e);
                if (ex[idx] <= 0) return;
            } else {
                next_height = min(next_height, h[e.to] + 1);
            }
        }
        if (cnt[h[idx]] > 1) {
            update_height(idx, next_height);
        } else {
            for (; high >= h[idx]; hs[high--].clear()) {
                for (int j : hs[high]) update_height(j, g.size() + 1);
            }
        }
    }

public:

    const T INF;
    int relabels, high;
    vector<T> ex;
    vector<int> cnt, h;
    vector<vector<int>> hs;
    vector<vector<edge>> g;

    PushRelabel(int n) : INF(numeric_limits<T>::max()), g(n), hs(n + 1), high(0) {}

    void add_edge(int from, int to, T cap, int idx = -1) {
        g[from].emplace_back(to, cap, g[to].size(), false, idx);
        g[to].emplace_back(from, 0, g[from].size() - 1, true, idx);
    }

    T max_flow(int s, int t) {
        ex.assign(g.size(), 0);
        ex[s] = INF;
        ex[t] = -INF;
        global_relabel(t);
        for (auto& e : g[s]) push(s, e);
        for (; high >= 0; --high) {
            while (!hs[high].empty()) {
                int idx = hs[high].back();
                hs[high].pop_back();
                discharge(idx);
                if (relabels >= g.size() * 4) global_relabel(t);
            }
        }
        return ex[t] + INF;
    }

    void reset() {
        for (auto& es : g) for (auto& e : es) if (!e.isrev) {
            e.cap = e.cap + g[e.to][e.rev].cap;
            g[e.to][e.rev].cap = 0;
        }
    }

    void print() {
        for (int i = 0; i < g.size(); ++i) for (auto& e : g[i]) if (!e.isrev) {
            auto& rev_e = g[e.to][e.rev];
            cout << i << " -> " << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
        }
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int V, E;
    cin >> V >> E;
    PushRelabel<int> g(V);
    REP (i, E) {
        int u, v, c;
        cin >> u >> v >> c;
        g.add_edge(u, v, c);
    }
    cout << g.max_flow(0, V - 1) << endl;
}


Measured memory_bytes: 3300