// CHAT GPT 4
#include <iostream>
#include <cstdio>
#include <vector>
#include <limits>
#include <queue>
#include <climits>

using namespace std;

struct Edge {
    int to, rev, flow, cap;
};

class Graph {
    int n;
    vector<int> h, e, cur;
    vector<vector<Edge>> g;

    void add_edge_internal(int from, int to, int cap) {
        g[from].push_back({to, (int) g[to].size(), 0, cap});
        g[to].push_back({from, (int) g[from].size() - 1, 0, 0});
    }

    void push(Edge &edge, int u, int v) {
        int flow = min(e[u], edge.cap - edge.flow);
        edge.flow += flow;
        g[v][edge.rev].flow -= flow;
        e[u] -= flow;
        e[v] += flow;
    }

    void relabel(int u) {
        h[u] = 2e9;
        for (auto &edge : g[u]) {
            if (edge.cap - edge.flow > 0) {
                h[u] = min(h[u], h[edge.to] + 1);
            }
        }
    }

    vector<int> find_max_height_vertices(int source, int dest) {
        vector<int> max_height;
        for (int i = 0; i < n; i++) {
            if (i != source && i != dest && e[i] > 0) {
                if (!max_height.empty() && h[i] > h[max_height[0]]) {
                    max_height.clear();
                }
                if (max_height.empty() || h[i] == h[max_height[0]]) {
                    max_height.push_back(i);
                }
            }
        }
        return max_height;
    }

public:
    Graph(int n) : n(n), h(n), e(n), cur(n), g(n) {}

    void add_edge(int from, int to, int cap) {
        add_edge_internal(from, to, cap);
        add_edge_internal(to, from, 0);
    }

    int max_flow(int source, int dest) {
        h[source] = n;
        e[source] = INT_MAX;
        for (auto &edge : g[source]) {
            push(edge, source, edge.to);
        }

        while (true) {
            auto max_height = find_max_height_vertices(source, dest);
            if (max_height.empty())
                break;

            for (auto i : max_height) {
                bool pushed = false;
                for (int j = cur[i]; j < g[i].size() && e[i]; j++) {
                    auto &edge = g[i][j];
                    if (edge.cap - edge.flow > 0 && h[i] == h[edge.to] + 1) {
                        push(edge, i, edge.to);
                        pushed = true;
                    }
                    cur[i] = j;
                }

                if (!pushed) {
                    relabel(i);
                    cur[i] = 0;
                }
            }
        }

        int max_flow = 0;
        for (auto &edge : g[source])
            max_flow += edge.flow;

        return max_flow;
    }
};


int main() {
    int n, m, x, y, z;
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    cin >> n >> m;
    Graph g(n);
    for(int i = 1; i <= m; i ++) {
        cin >> x >> y >> z;
        x--;
        y--;

        g.add_edge(x, y, z);
    }

    cout << g.max_flow(0, n-1) << '\n';
    return 0;
}