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

ifstream ccin("maxflow.in");
ofstream ccout("maxflow.out");

int main() {
    ios_base::sync_with_stdio(false);

    int n, m;
    ccin >> n >> m;

    vector<int> from(2*m), to(2*m), cap(2*m), inv(2*m);
    vector<int> prv(n + 1), leaf;
    vector<vector<int>> G(n + 1);
    int src = 1, sink = n;

    for (int i = 0; i < m; i++) {
        ccin >> from[i] >> to[i] >> cap[i];
        from[m+i] = to[i]; to[m+i] = from[i]; cap[m+i] = 0;
        inv[i] = m+i; inv[m+i] = i;
        G[from[i]].push_back(i);
        G[to[i]].push_back(m+i);
        if (to[i] == sink) {
            leaf.push_back(i);
        }
    }

    auto neighbour = [&](int x, int edge) {
        return x^from[edge]^to[edge];
    };

    auto bfs = [&]() {
        for (int i = 1; i <= n; i++) prv[i] = -1;
        queue<int> q; q.push(src);
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (auto edge : G[x]) {
                int y = neighbour(x, edge);
                if (prv[y] == -1 && cap[edge] > 0) {
                    prv[y] = edge;
                    q.push(y);
                }
            }
        }
        return prv[sink] != -1;
    };

    auto add_path = [&](int edge) {
        int p = neighbour(sink, edge), m = cap[edge];
        while (p != src) {
            m = min(m, cap[prv[p]]);
            p = neighbour(p, prv[p]);
        }
        if (!m) return 0;
        cap[edge] -=m;
        cap[inv[edge]] += m;
        p = neighbour(sink, edge);
        while (p != src) {
            cap[prv[p]] -= m;
            cap[inv[prv[p]]] += m;
            p = neighbour(p, prv[p]);
        }
        return m;
    };

    int mf = 0;
    while(bfs()) for(auto it : leaf) mf += add_path(it);
    ccout << mf << '\n';

    return 0;
}