#include <bits/stdc++.h>

class Dinic {
    struct Edge {
        int from, to, cap, flow;
        Edge(int from, int to, int cap)
            : from(from), to(to), cap(cap), flow() {}
        int residue() const { return cap - flow; }
    };

    static constexpr int INF = 1e9;
    int N, s, t, lim;
    std::vector<Edge> edges;
    std::vector<std::vector<int>> adj;
    std::vector<int> ptr, lvl;
    bool scaling;

    bool build_level_graph() {
        fill_n(lvl.begin(), N, -1);
        std::queue<int> q({ s });
        lvl[s] = 1;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int id : adj[u]) {
                Edge &e = edges[id];
                if (lvl[e.to] == -1 && e.residue() >= lim) {
                    lvl[e.to] = lvl[u] + 1;
                    q.push(e.to);
                }
            }
        }

        return lvl[t] != -1;
    }

    int push_flow(int u, int flow = INF) {
        if (u == t || !flow) return flow;
        for (; ptr[u] < (int)adj[u].size(); ++ptr[u]) {
            Edge &e = edges[adj[u][ptr[u]]], &rev = edges[adj[u][ptr[u]] ^ 1];
            if (lvl[e.to] != lvl[u] + 1) continue;
            int f = push_flow(e.to, std::min(flow, e.residue()));
            if (!f) continue;
            e.flow += f; rev.flow -= f;
            return f;
        }
        return 0;
    }

public:
    Dinic(int N, int s, int t, bool scaling = true)
        : N(N), s(s), t(t), edges(), adj(N), ptr(N), lvl(N), scaling(scaling) {}

    void add_edge(int u, int v, int cap) {
        adj[u].push_back(edges.size());
        adj[v].push_back(edges.size() + 1);
        edges.emplace_back(u, v, cap);
        edges.emplace_back(v, u, 0);
    }

    int max_flow() {
        int flow = 0;
        for (lim = (scaling ? 1 : (1 << 30)); lim; lim >>= 1) {
            while (build_level_graph()) {
                fill_n(ptr.begin(), N, 0);
                while (int f = push_flow(s)) flow += f;
            }
        }
        return flow;
    }
};

int main() {
    std::ifstream fin("maxflow.in");
    std::ofstream fout("maxflow.out");

    int N, M;
    fin >> N >> M;

    Dinic dinic(N, 0, N - 1);
    for (int i = 0; i < M; ++i) {
        int u, v, cap;
        fin >> u >> v >> cap;
        dinic.add_edge(u - 1, v - 1, cap);
    }

    fout << dinic.max_flow();

    fin.close();
    fout.close();
    return 0;
}