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

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] || capacitate[i][j] == flux[i][j])
                continue;

            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)) {
        int capRezMin = INT_MAX;
        int aux = n - 1;

        while (tata[aux] != -1) {
            capRezMin = std::min(capRezMin, capacitate[tata[aux]][aux] - flux[tata[aux]][aux]);
            aux = tata[aux];
        }
        fluxMaxim += capRezMin;

        aux = n - 1;
        while (tata[aux] != -1) {
            flux[aux][tata[aux]] -= capRezMin;
            flux[tata[aux]][aux] += capRezMin;
            aux = tata[aux];
        }
    }

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

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