#include <bits/stdc++.h>

using namespace std;

/** Push-Relabel??????????????§??????????????????. ?¨???????O(V^2 sqrt(E). */
/**
 usage: 0??????V-1???????????§???????±?????????¨???
    int main() {
        int V, E; cin >> V >> E;
        Network g(V);
        for (auto i = 0; i < E; i++) {
            int u, v, c;
            cin >> u >> v >> c;
            g.addEdge(u, v, c);
        }
        cout << g.maxFlow(0, V - 1) << endl;
    }
*/
template<typename T>
struct Network {
    static const T INF = numeric_limits<T>::max() >> 12;
    struct Edge {
        int from, to;
        T cap;
        Edge* rev;
        Edge(int from, int to, T cap) :
            from(from), to(to), cap(cap) {}
    };
    vector<Edge*> edges;
    vector<vector<Edge*>> graph;
    Network(int N) : graph(N, vector<Edge*>()) {}
    ~Network() { 
        for (auto e : edges) delete(e);
    }
    void addEdge(int s, int t, T cap) {
        auto e = new Edge(s, t, cap);
        auto r = new Edge(t, s, 0);
        edges.push_back(e); edges.push_back(r);
        e->rev = r; r->rev = e;
        graph[s].push_back(e); graph[t].push_back(r);
    }
    T maxFlow(int s, int t) {
        const int N = graph.size();
        vector<int> label(N, 0); label[s] = N;
        vector<T> excess(N, 0);
        int level = 0;
        for (auto e : graph[s]) {
            auto gamma = e->cap;
            e->cap = 0;
            e->rev->cap = gamma;
            excess[e->from] -= gamma;
            excess[e->to] += gamma;
        }
        vector<vector<int>> L(2*N, vector<int>()); {
            for (int i = 0; i < N; i++) if (i != s and i != t and excess[i] > 0) {
                L[0].push_back(i);
            }
        }
        auto push = [&](Edge* e) {
            auto gamma = min(excess[e->from], e->cap);
            if (gamma == 0) return;
            e->cap -= gamma;
            e->rev->cap += gamma;
            int u = e->from; int v = e->to;
            if (u != s and u != t and excess[u] == gamma) {
                assert(not L[label[u]].empty());
                L[label[u]].pop_back();
            }
            if (v != s and v != t and excess[v] == 0) L[label[v]].push_back(v);
            excess[u] -= gamma; excess[v] += gamma;
        };
        auto relabel = [&](int v) {
            assert(not L[level].empty());
            L[level].pop_back();
            label[v] = 1<<28;
            for (auto e : graph[v]) {
                if (e->cap <= 0) continue;
                int w = e->to;
                label[v] = min(label[v], label[w] + 1);
            };
            L[label[v]].push_back(v);
            level = label[v];
        };
        while (level >= 0) {
            if (L[level].empty()) { level--; continue; }
            auto v = L[level].back();
            bool used = false;
            for (auto e : graph[v]) {
                if (label[e->from] == label[e->to] + 1 and e->cap > 0) {
                    used = true;
                    push(e);
                }
            }
            if (not used) {
                relabel(v);
            }
        }
        return excess[t];
    }
};

int main() {
    int V, E; cin >> V >> E;
    Network<int> network(V);
    for (int i = 0; i < E; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        network.addEdge(u, v, c);
    }
    cout << network.maxFlow(0, V - 1) << endl;
    return 0;
}

Measured memory_bytes: 3236