#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

void citire(std::vector<std::vector<std::pair<int, int> > > &graf, int &n) {
    int m;
    int u, v, capacitate;
    std::ifstream f("maxflow.in");
    f >> n >> m;
    graf.assign(n, std::vector<std::pair<int, int> >(n, {0, 0}));
    while (m--) {
        f >> u >> v >> capacitate;
        graf[u - 1][v - 1] = {0, capacitate}; // {flux, capacitate}
    }
    f.close();
}

void afisareLant(std::vector<std::vector<std::pair<int, int> > > &graf, std::vector<int> &tata, int node) {
    while (tata[node] != INT_MAX) {
        if (tata[node] < 0) {
            std::cout << "(" << node << "-" << -tata[node] << ", ";
            std::cout << graf[node][-tata[node]].first << ") ";
            node = -tata[node];
        } else {
            std::cout << "(" << tata[node] << "-" << node << ", ";
            std::cout << graf[tata[node]][node].second - graf[tata[node]][node].first << ") ";
            node = tata[node];
        }
    }
    std::cout << "\n";
}

int capacitateMinima(std::vector<std::vector<std::pair<int, int> > > &graf, std::vector<int> &tata, int node) {
    int capMin = INT_MAX;
    while (tata[node] != INT_MAX) {
        if (tata[node] < 0) {
            capMin = std::min(capMin, graf[node][-tata[node]].first);
            node = -tata[node];
        } else {
            capMin = std::min(capMin, graf[tata[node]][node].second - graf[tata[node]][node].first);
            node = tata[node];
        }
    }
    return capMin;
}

void revizuireFlux(std::vector<std::vector<std::pair<int, int> > > &graf, std::vector<int> &tata, int node,
                   const int capMin) {
    while (tata[node] != INT_MAX) {
        if (tata[node] < 0) {
            graf[node][-tata[node]].first -= capMin;
            node = -tata[node];
        } else {
            graf[tata[node]][node].first += capMin;
            node = tata[node];
        }
    }
}

bool lantNesaturat(std::vector<std::vector<std::pair<int, int> > > &graf, std::vector<int> &tata, const int n,
                   const int s) {
    std::queue<int> q;
    std::vector viz(n, false);
    q.push(s);
    viz[s] = true;
    while (!q.empty()) {
        const int u = q.front();
        q.pop();
        for (int v = 0; v < n; ++v)
            if (!viz[v]) {
                if (graf[u][v].second - graf[u][v].first > 0) {
                    tata[v] = u;
                    if (v == n - 1)
                        return true;
                    viz[v] = true;
                    q.push(v);
                } else if (graf[v][u].first > 0) {
                    tata[v] = -u;
                    if (v == n - 1)
                        return true;
                    viz[v] = true;
                    q.push(v);
                }
            }
    }
    return false;
}

void edmondsKarp() {
    std::vector<std::vector<std::pair<int, int> > > graf;
    int n;
    citire(graf, n);

    std::vector tata(n, INT_MAX);
    int fluxMaxim = 0;

    while (lantNesaturat(graf, tata, n, 0)) {
        // afisareLant(graf, tata, n - 1);

        const int capMin = capacitateMinima(graf, tata, n - 1);
        // std::cout << "capMin=" << capMin << "\n";
        revizuireFlux(graf, tata, n - 1, capMin);

        std::fill(tata.begin(), tata.end(), INT_MAX);
        fluxMaxim += capMin;
    }
    // std::cout << "FLUX MAXIM: " << fluxMaxim;
    std::ofstream g("maxflow.out");
    g<<fluxMaxim;
    g.close();
}

int main() {
    edmondsKarp();
    return 0;
}