#include <bits/stdc++.h>

using flow_type = int;

struct push_relabel {
    struct edge {
        int s, d;
        flow_type c, f;
        int r;
    };
    int n, s, t;
    std::vector<std::vector<edge>> g;
    std::vector<int> excess, height, seen;
    std::priority_queue<std::pair<int, int>> queue;
    std::vector<std::pair<std::pair<int, int>, flow_type>> edges;

    push_relabel(int n_ = 0) : n(n_) {}

    // Compute the maximum-flow from `s_` to `t_` by Dinic's algorithm.
    flow_type maximum_flow(int s, int t) {
        make_graph();
        excess.assign(n, 0);
        height.assign(n, 0);
        seen.assign(n, 0);
        height[s] = n;
        for (auto &e : g[s]) {
            excess[s] += e.c;
            push(e);
        }
        while (queue.size()) {
            int u = queue.top().second;
            queue.pop();
            if (u != s && u != t) discharge(u);
        }
        flow_type res = 0;
        for (auto &e : g[s]) res += e.f;
        return res;
    }

    // Add an edge from `u` to `v` with capacity `c`. Note that the edge will be
    // added to `g` when `make_graph` was called instead of just after calling
    // this function.
    void add_edge(int u, int v, flow_type c) {
        if (u != v && c != 0) {
            edges.emplace_back(std::make_pair(u, v), c);
        }
    }

    // OK
    void make_graph() {
        g.assign(n, {});
        std::sort(edges.begin(), edges.end());
        for (auto it = edges.begin(); it != edges.end();) {
            flow_type c = 0;
            auto uv = it->first;
            while (it != edges.end() && it->first == uv) {
                c += it->second;
                ++it;
            }
            int u = uv.first, v = uv.second;
            g[u].push_back({u, v, c, 0, (int)g[v].size()});
            g[v].push_back({v, u, 0, 0, (int)g[u].size() - 1});            
        }
    }

    // OK
    void push(edge &e) {
        int u = e.s, v = e.d;
        flow_type send = std::min(excess[u], residue(e));
        e.f += send;
        reverse(e).f -= send;
        excess[u] -= send;
        excess[v] += send;
        if (excess[v] > 0) queue.emplace(height[v], v);
        if (excess[u] > 0) queue.emplace(height[u], u);
    }

    // OK
    void discharge(int u) {
        while (excess[u] > 0) {
            if (seen[u] < (int)g[u].size()) {
                edge &e = g[u][seen[u]];
                if (residue(e) > 0 && height[u] == height[e.d] + 1) {
                    push(e);
                } else {
                    ++seen[u];
                }
            } else {
                relabel(u);
                seen[u] = 0;
            }
        }
    }

    // OK
    void relabel(int u) {
        int minheight = n * 2;
        for (auto &e : g[u]) {
            if (residue(e) > 0) {
                minheight = std::min(minheight, height[e.d]);
            }
        }
        height[u] = minheight + 1;
        queue.emplace(height[u], u);
    }

    flow_type residue(const edge &e) { return e.c - e.f; }

    edge &reverse(const edge &e) { return g[e.d][e.r]; }

    void show() {
        for (auto &es : g) {
            for (auto &e : es) {
                printf("%d -> %d, %d\n", e.s, e.d, e.f);
            }
        }
    }
};

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

int main() {
    int N, M;
    while (cin >> N >> M) {
        push_relabel g(N);
        for(int i = 0; i < M; ++i){
            int a, b, c;
            cin >> a >> b >> c;
            g.add_edge(a, b, c);
        }
        cout << g.maximum_flow(0, N-1) << endl;
        // g.show();
    }
}

Measured memory_bytes: 3188