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

///Time complexity: O(V * E^2)
using Graph = std::vector<std::vector<int>>;
int DIM;
const int inf = INT_MAX;

bool bfs(int source, int target, std::vector<int>& level, const Graph& residualGraph) {
    std::ranges::fill(level, -1);
    std::queue<int> q;
    q.push(source);
    level[source] = 0;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        for (int i{1}; i <= DIM; ++i)
            if (x != i && residualGraph[x][i] > 0 && level[i] < 0)
                level[i] = level[x] + 1, q.push(i);
    }

    return level[target] >= 0;
}

int sendFlow(int source, int target, int flow, Graph& residualGraph, std::vector<int>& level, std::vector<int>& count) {
    if (source == target)
        return flow;

    if (count[source] == residualGraph[source].size()) /// evit din timp un dead end
        return 0;

    for (int i{1}; i <= DIM; ++i)
        if (residualGraph[source][i] > 0) {
            count[source] ++;
            if (level[source] + 1 == level[i]) {
                int curr_flow = std::min(flow, residualGraph[source][i]);

                int min_cap = sendFlow(i, target, curr_flow, residualGraph, level, count);
                if (min_cap > 0) {
                    residualGraph[source][i] -= min_cap;
                    residualGraph[i][source] += min_cap;

                    return min_cap;
                }
            }
        }

    return 0;
}

int dinic(int source, int target, Graph& graph) { ///target sau sink
    if (source == target)
        return -1;

    int maxFlow{};
    Graph residualGraph = graph;
    std::vector<int> level(DIM + 1, -1);
    ///there is still a path from source to sink(construct the level graph in bfs)
    while (bfs(source, target, level, residualGraph)) {
        std::vector<int> count(DIM + 1, 0);
        while (int flow = sendFlow(source, target, inf, residualGraph, level, count))
            maxFlow += flow;
    }

    return maxFlow;
}

int main() {
    int m;
    std::ifstream fin("maxflow.in");
    fin >> DIM >> m;
    Graph graph{};
    graph.resize(DIM + 1, std::vector<int>(DIM + 1));
    while (m --) {
        int x, y, val;
        fin >> x >> y >> val;
        graph[x][y] = val;
    }

    std::ofstream fout("maxflow.out");
    fout << dinic(1, DIM, graph);
}