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

void citire(std::vector<std::vector<int> > &graf, std::vector<std::vector<int> > &capacitate,
        std::vector<std::vector<int> > &flux, int& n) {
    int m;
    int i, j, w;
    std::ifstream f("maxflow.in");
    f >> n >> m;
    graf.resize(n);
    capacitate.resize(n, std::vector(n, 0));
    flux.resize(n, std::vector(n, 0));
    while (m--) {
        f >> i >> j >> w;
        capacitate[i - 1][j - 1] = w;
        graf[i - 1].push_back(j - 1);
        graf[j - 1].push_back(i - 1);
    }
    f.close();
}

bool bfs(std::vector<std::vector<int> > &graf, std::vector<std::vector<int> > &capacitate,
        std::vector<std::vector<int> > &flux, std::vector<int>& tata, const int n) {
    std::vector viz(n, false);
    std::queue<int> q;
    q.push(0);
    viz[0] = true;

    while (!q.empty()) {
        const int i = q.front();
        q.pop();
        for (const auto &j: graf[i])
            if (!viz[j])
                if (capacitate[i][j] - flux[i][j] > 0) {
                    tata[j] = i;
                    if (j == n - 1)
                        return true;
                    q.push(j);
                    viz[j] = true;
                }
    }
    return false;
}

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

    int fluxMaxim = 0;
    std::vector tata(n, -1);
    while (bfs(graf, capacitate, flux, tata, n)) {
        std::vector<int> drum;
        int aux = n - 1;
        while (aux != -1) {
            drum.push_back(aux);
            aux = tata[aux];
        }
        std::ranges::reverse(drum);

        int capRezMin = 1e9;
        for (int i = 0; i < static_cast<int>(drum.size()) - 1; ++i) {
            const int u = drum[i];
            const int v = drum[i + 1];
            capRezMin = std::min(capRezMin, capacitate[u][v] - flux[u][v]);
        }
        for (int i = 0; i < static_cast<int>(drum.size()) - 1; ++i) {
            const int u = drum[i];
            const int v = drum[i + 1];
            flux[u][v] += capRezMin;
            flux[v][u] -= capRezMin;
        }
        fluxMaxim += capRezMin;
        std::ranges::fill(tata, -1);
    }

    std::ofstream g("maxflow.out");
    g<<fluxMaxim;
    g.close();
}

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