#include <queue>
#include <vector>
#include <limits>
#include <iostream>

struct PushRelabel {
    int V;
    std::vector <std::basic_string<int>> G;
    std::vector <std::vector <int>> flow, c;
    std::vector <int> height, excess, seen;
    std::queue <int> excess_v;

    PushRelabel(int V) : V(V) {
        G.assign(V, std::basic_string<int>());
        c.assign(V, std::vector<int>(V, 0));
        flow.assign(V, std::vector<int>(V, 0));
        height.assign(V, 0);
        excess.assign(V, 0);
        seen.assign(V, 0);
    }

    void addEdge(int u, int v, int cap) {
        G[u].push_back(v);
        G[v].push_back(u);
        c[u][v] += cap; 
    }

    void push(int u, int v) {
        int d = std::min(excess[u], c[u][v]);
        flow[u][v] += d; flow[v][u] -= d;
        excess[u] -= d; excess[v] += d;
        if (d && excess[v] == d)
            excess_v.emplace(v);
    }

    void relabel(int u) {
        int d = std::numeric_limits<int>::max();
        for (int v = 0; v < V; ++v)
            if (c[u][v] - flow[u][v]) {
                d = std::min(d, height[v]);
            }

        if (d < std::numeric_limits<int>::max())
            height[u] = d + 1;
    }

    void discharge(int u) {
        while (excess[u]) {
            if (seen[u] < V) {
                int v = seen[u];
                if (c[u][v] - flow[u][v] > 0 && height[u] > height[v]) push(u, v);
                else ++seen[u];
            } else {
                relabel(u);
                seen[u] = 0;
            }
        }
    }

    int MaxFlow(int s, int t) {
        height[s] = V;
        excess[s] = std::numeric_limits<int>::max();

        for (const int &u : G[s]) {
            if (u != s) push(s, u);
        }

        while (!excess_v.empty()) {
            int u = excess_v.front();
            excess_v.pop();
            if (u != s && u != t) discharge(u);
        }

        int max_flow = 0;
        for (int i = 0; i < V; ++i)
            max_flow += flow[i][t];

        return max_flow;
    }
};

void Open() {
#ifndef ONLINE_JUDGE
    (void)!freopen("maxflow.in", "r", stdin);
    (void)!freopen("maxflow.out", "w", stdout);
#endif
}

int main() {
    Open();

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); 

    int n, m; std::cin >> n >> m;
    PushRelabel pr(n);


    for (int i = 0; i < m; ++i) {
        int u, v, cap; std::cin >> u >> v >> cap;
        pr.addEdge(u - 1, v - 1, cap);
    }

    std::cout << pr.MaxFlow(0, n - 1) << '\n';
    return 0;
}