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

using namespace std;

int n, m;
vector <vector <int>> g;

bool bfs(vector <vector <int>> rg, int s, int& t, vector <int>& parent) {
    vector <bool> visited(n);
    queue <int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; v++) {
            if (!visited[v] && rg[u][v] > 0) {
                parent[v] = u;
                if (v == t) {
                    return true;
                }
                q.push(v);
                visited[v] = true;
            }
        }
    }
    return false;
}

int ford_fulkerson(vector <vector <int>> g, int s, int t) {
    int u, v;
    vector <vector <int>> rg(n);
    for (u = 0; u < n; u++) {
        rg[u].resize(n);
        for (v = 0; v < n; v++)
            rg[u][v] = g[u][v];
    }
    vector <int> parent(n);
    int max_flow = 0;
    while (bfs(rg, s, t, parent)) {
        int path_flow = INT_MAX;
        for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            path_flow = min(path_flow, rg[u][v]);
        }
        for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            rg[u][v] -= path_flow;
            rg[v][u] += path_flow;
        }
        max_flow += path_flow;
    }
    return max_flow;
}

int main() {
    setlocale(LC_ALL, "rus");

    ifstream rd;
    rd.open("graph.txt");

    rd >> n >> m;

    g.resize(n);
    for (int i = 0; i < n; i++)
        g[i].resize(n, 0);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        rd >> u >> v >> w;
        g[u][v] = w;
    }

    cout << "Максимальный поток: " << ford_fulkerson(g, 0, n - 1) << endl;

    system("pause");
    return 0;
}