/* Дан неориентированный связный граф.
 * Требуется найти вес минимального остовного дерева в этом графе с помощью алгоритма Борувки.*/
// T(N, M) = O(|E|log|V|)
// M(N, M) = O(|V| + |E|)

#include <bits/stdc++.h>
using namespace std;
const int INF = 2000000000; // константа, отвечающая за "бесконечность".
typedef unsigned long long ull;


class Graph {
    // <пропускная способность, поток>
    vector <vector<pair<int, int> > > g;
    int vertices;

    void InsertEdge_(int from, int to, int capacity, int flow) {
        g[from][to] = {capacity, flow};
    }


    void CreateLists_(int VerticesNumber) {
        vertices = VerticesNumber;
        g.resize((ull)VerticesNumber);
        for (int i = 0; i < VerticesNumber; i++)
            g[i].resize((ull)VerticesNumber, {0, 0});
    }

    vector <tuple<int, int, int> > adjacent_(int v) {
        vector <tuple<int, int, int> > result;
        for (int i = 0; i < vertices; i++) {
            if (g[v][i].first > 0)
                result.push_back(make_tuple(i, g[v][i].first, g[v][i].second));
        }
        return result;
    }

    int findBlockingFlow_() {
        vector <int> pointers;
        pointers.assign(g.size(), 0);
        int getFlow = 0, resultFlow = 0;
        do {
            getFlow = dfs(0, INF, *this, pointers);
            resultFlow += getFlow;
        } while (getFlow > 0);
        return resultFlow;
    }

public:

    Graph(int size) {
        CreateLists_(size);
    }

    friend istream& operator >>(istream& in, Graph& g) {
        int VerticesNumber, EdgesNumber;
        in >> VerticesNumber >> EdgesNumber;
        g.CreateLists(VerticesNumber);
        for (int i = 0; i < EdgesNumber; i++) {
            int from, to, capacity;
            in >> from >> to >> capacity;
            g.InsertEdge(from, to, capacity, 0);
        }
        return in;
    }

    friend ostream& operator <<(ostream& out, Graph& g) {
        out << "Graph. \n";
        out << g.vertices << " " << '\n';
        for (int i = 0; i < g.vertices; i++) {
            out << i << ":\n";
            for (auto to: g.adjacent_(i))
                out << get<0>(to) << " " << get<1>(to) << " " << get<2>(to) << '\n';
            out << '\n';
        }
        return out;
    }

    void InsertEdge(int from, int to, int capacity, int flow) {
        InsertEdge_(from, to, capacity, flow);
    }

    void CreateLists(int VerticesNumber) {
        CreateLists_(VerticesNumber);
    }

    int findBlockingFlow() {
        return findBlockingFlow_();
    }

    void addFlow(Graph &from) {
        for (int v = 0; v < from.size(); v++) {
            for (auto to: from.adjacent(v)) {
                if (g[v][get<0>(to)].first > 0) {
                    g[v][get<0>(to)].first -= from.g[v][get<0>(to)].second;
                    g[get<0>(to)][v].first += from.g[v][get<0>(to)].second;
                }
            }
        }
    }

    int size() {
        return vertices;
    }

    vector <tuple<int, int, int> > adjacent(int v) {
        return adjacent_(v);
    }

    friend int dfs(int, int, Graph&, vector<int>&);

    Graph() = default;
    Graph(const Graph&) = default;
    Graph& operator=(const Graph&) = delete;
};


pair<Graph, int> LayeredNetwork(Graph &g) {
    Graph res(g.size());
    queue <int> q;
    vector <int> visited, distance;
    visited.assign(g.size(), 0);
    distance.assign(g.size(), INF);
    q.push(0);
    distance[0] = 0;
    visited[0] = 1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto to: g.adjacent(v)) {
            if (!visited[get<0>(to)]) {
                q.push((int)get<0>(to));
                visited[get<0>(to)] = 1;
                distance[get<0>(to)] = distance[v] + 1;
            }
            if (distance[get<0>(to)] == distance[v] + 1)
                res.InsertEdge(v, get<0>(to), get<1>(to), get<2>(to));
        }
    }
    return {res, distance[g.size() - 1]};
}


int dfs(int v, int flow, Graph &graph, vector <int>& pointers) {
    //cout << v << " ";
    if (v == graph.size() - 1)
        return flow;
    if (flow == 0)
        return 0;
    int size = graph.size();
    for (int i = pointers[v]; i < size; i++) {
        pointers[v]++;
        if (graph.g[v][i].first > 0) {
            int foundedFlow = dfs(i,
                                  min(flow, graph.g[v][i].first - graph.g[v][i].second),
                                  graph, pointers);
            graph.g[v][i].second += foundedFlow;
            if (foundedFlow)
                return foundedFlow;
        }
    }
    return 0;
}


class Dinic {
    int maxflow = 0;

    void Dinic_(Graph &g) {
        bool isPath = true;
        int n = g.size();
        for(int i = 0; i < n - 1; i++) {
            auto temp = LayeredNetwork(g);
            if (temp.second == INF)
                break;
            Graph gLayered = temp.first;
            //cout << gLayered;
            maxflow += gLayered.findBlockingFlow();
            //cout << gLayered;
            g.addFlow(gLayered);
            //cout << g;
            //g = ResidualNetwork(g);
        }
    }

public:
    Dinic(Graph &g) {
        Dinic_(g);
    }

    // Вывод ответа в поток вывода.
    friend ostream& operator <<(ostream& out, Dinic& D) {
        return out << D.maxflow << '\n';
    }

    Dinic() = default;
    Dinic& operator=(const Dinic&) = delete;
};

// Функция для решения поставленной задачи. Считывает граф, применяет на нём алгоритм
// Борувки и выводит ответ, хранящийся в объекте mst класса Dinic.
void solve() {
    Graph g;
    cin >> g;
    Dinic d(g);
    cout << d;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 3320