Sem_2_Task_7

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

struct Edge;

const int64_t INF = int64_t(1e15);

namespace {
    using NumsVec = std::vector<int64_t>;
    using VecNumsVec = std::vector<NumsVec>;
    using BoolVec = std::vector<bool>;
    using EdgeVec = std::vector<Edge>;
    using VecEdgeVec = std::vector<EdgeVec>;
    using UnMapNumEdge = std::unordered_map<int64_t, Edge>;
}

struct Edge {
    Edge() = default;
    Edge(std::pair<size_t, size_t> edge) : from(edge.first), to(edge.second) {};
    Edge(size_t i, size_t j, size_t w) : from(i), to(j), c(w) {};

    bool operator==(const Edge& other) const {
        return from == other.from && to == other.to;
    }

    Edge Reverse() {
        return Edge(to, from, c);
    }

    size_t from = 0;
    size_t to = 0;
    int64_t c = 0;
};

std::istream& operator>>(std::istream& input, Edge& edge) {
    input >> edge.from >> edge.to >> edge.c;
    --edge.from;
    --edge.to;
    return input;
}

void InputEdges(std::vector<Edge>& edges) {
    for (auto& edge : edges) {
        std::cin >> edge;
    }
}

template<>
struct std::hash<Edge> {
    size_t operator()(const Edge& p) const {
        return p.from * p.to;
    }
};

std::ostream& operator<<(std::ostream& output, NumsVec& vec) {
    for (auto elem : vec) {
        std::cout << elem + 1 << " ";
    }
    return output;
}

struct Graph {
    Graph(size_t n) : size(n), neighbours(n), visited(n, false), color(n, 0),
    top_sort(n, 0), top_sort_pos(n - 1), d(n, INF) {};

    Graph(size_t n, EdgeVec& edges) : size(n), d(n, INF), flow(n, NumsVec(n, 0)), neighbours(n) {
        for (auto edge : edges) {
            auto& edge_direct = neighbours[edge.from][edge.to];
            edge_direct.from = edge.from;
            edge_direct.to = edge.to;
            edge_direct.c += edge.c;
            auto& edge_back = neighbours[edge.to][edge.from];
            edge_back.to = edge.from;
            edge_back.from = edge.to;
        }
    };

    size_t size = 0;
    bool cycle = false;

    std::vector<UnMapNumEdge> neighbours;
    VecNumsVec matrix;
    VecNumsVec flow;
    BoolVec visited;
    NumsVec color;
    NumsVec top_sort;
    NumsVec d;
    EdgeVec route;
    size_t max_flow = 0;
    size_t sum_w = 0;
    size_t top_sort_pos = 0;
};

bool Bfs(Graph& g, size_t s, size_t f) {
    NumsVec dist(g.size, INF);
    NumsVec parent(g.size, s);
    dist[s] = 0;
    std::queue<size_t> q;
    q.push(s);
    while (!q.empty()) {
        size_t cur = q.front();
        q.pop();
        for (auto [v, edge] : g.neighbours[cur]) {
            if (edge.c - g.flow[cur][v] > 0 && dist[v] > dist[cur] + 1) {
                dist[v] = dist[cur] + 1;
                parent[v] = cur;
                q.push(v);
            }
        }
    }
    if (dist[f] == INF) {
        return false;
    }
    EdgeVec way;
    size_t cur = f;
    while (cur != s) {
        way.push_back(g.neighbours[parent[cur]][cur]);
        cur = parent[cur];
    }
    std::reverse(way.begin(), way.end());
    g.route = way;
    return true;
}

void EdmondsKarp(Graph& g, size_t s, size_t t) {
    while (Bfs(g, s, t)) {
        int64_t cf = INF;
        for (auto edge : g.route) {
            cf = std::min(cf, edge.c - g.flow[edge.from][edge.to]);
        }
        for (auto edge : g.route) {
            g.flow[edge.from][edge.to] += cf;
            g.flow[edge.to][edge.from] = -g.flow[edge.from][edge.to];
        }
        g.max_flow += cf;
    }
}

int main() {
    size_t n, m;
    std::cin >> n >> m;
    EdgeVec edges(m);
    InputEdges(edges);
    Graph g(n, edges);
    EdmondsKarp(g, 0, n - 1);
    std::cout << g.max_flow;
}