#include <bits/stdc++.h>
using namespace std;

void printQueue(queue<int> q) {
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }

    cout << '\n';
}

bool BFS(vector<pair<int, int>> *forwardAdjacencyList, vector<pair<int,int>> *backwardAdjacencyList, vector<vector<pair<int, int>>> &capacityAndFlow, int *parentOf, int numberOfNodes, int startNode, int sinkNode) {
    bool isVisited[numberOfNodes];
    for (int i=0; i<numberOfNodes; i++)
        isVisited[i] = false;

    queue<int> workingQueue;
    workingQueue.push(startNode);
    isVisited[startNode] = true;

    cout<<'\n';
    while (not workingQueue.empty()) {
        int currentNode = workingQueue.front();
        cout<<currentNode<<'\n';
        workingQueue.pop();

//        cout<<"before 1\n";
        for (auto adjacentNode : forwardAdjacencyList[currentNode]) {
            if (capacityAndFlow[currentNode][adjacentNode.first].first -
                capacityAndFlow[currentNode][adjacentNode.first].second > 0) {
                if (adjacentNode.first == sinkNode) {
                    parentOf[sinkNode] = currentNode;
                    return true;
                } else if (not isVisited[adjacentNode.first]) {
                    workingQueue.push(adjacentNode.first);
                    parentOf[adjacentNode.first] = currentNode;
                    isVisited[adjacentNode.first] = true;
                }
            }
        }

//        printQueue(workingQueue);
//        cout<<"after 1\n";
        for (auto adjacentNode : backwardAdjacencyList[currentNode])
            if (capacityAndFlow[currentNode][adjacentNode.first].first - capacityAndFlow[currentNode][adjacentNode.first].second > 0) {
                if (adjacentNode.first == sinkNode) {
                    parentOf[sinkNode] = currentNode;
                    return true;
                }
                else if (not isVisited[adjacentNode.first]) {
                    workingQueue.push(adjacentNode.first);
                    parentOf[adjacentNode.first] = currentNode;
                    isVisited[adjacentNode.first] = true;
                }
            }
    }

    return false;
}


int getMaxFlowEdmondsKarp(vector<pair<int, int>> *forwardAdjacencyList, int numberOfNodes, int startNode, int sinkNode) {
    vector<vector<pair<int,int>>> capacityAndFlow(numberOfNodes, vector<pair<int, int>>(numberOfNodes, pair<int, int>()));
    vector<pair<int,int>> backwardAdjacencyList[numberOfNodes];

    for (int node = 0; node<numberOfNodes; node++)
        for (auto adjacentNode : forwardAdjacencyList[node]) {
            backwardAdjacencyList[adjacentNode.first].push_back({node, adjacentNode.second});

            capacityAndFlow[node][adjacentNode.first].first += adjacentNode.second;
            capacityAndFlow[node][adjacentNode.first].second += 0;

            capacityAndFlow[adjacentNode.first][node].first += adjacentNode.second;
            capacityAndFlow[adjacentNode.first][node].second += adjacentNode.second;
        }

    int parentOf[numberOfNodes], maxFlow = 0;
    while (BFS(forwardAdjacencyList, backwardAdjacencyList, capacityAndFlow, parentOf, numberOfNodes, startNode, sinkNode)) {
        int currentFlowUnits = INT_MAX;

        for (int i = 0; i<numberOfNodes; i++)
            cout<<parentOf[i]<<' ';
        cout<<'\n';
        for (int childNode = sinkNode; childNode!=startNode; childNode = parentOf[childNode]) {
            int parentNode = abs(parentOf[childNode]);

            if (capacityAndFlow[parentNode][childNode].first - capacityAndFlow[parentNode][childNode].second < currentFlowUnits)
                currentFlowUnits = capacityAndFlow[parentNode][childNode].first - capacityAndFlow[parentNode][childNode].second;
        }

        for (int childNode = sinkNode; childNode != startNode; childNode = parentOf[childNode]) {
            int parentNode = parentOf[childNode];

            capacityAndFlow[parentNode][childNode].second +=currentFlowUnits;
            capacityAndFlow[childNode][parentNode].second -=currentFlowUnits;
        }

        maxFlow +=currentFlowUnits;
//        cout<<currentFlowUnits<<'\n';
    }

    return maxFlow;
}


int main() {
    ifstream input("maxflow.in");

    int numberOfNodes, numberOfEdges;
    input>>numberOfNodes>>numberOfEdges;

    vector<pair<int, int>> adjacencyList[numberOfNodes];
    int parentNode, childNode, capacity;
    for (int i = 0; i<numberOfEdges; i++){
        input>>parentNode>>childNode>>capacity;
        parentNode--; childNode--;
        adjacencyList[parentNode].push_back({childNode, capacity});
    }

    input.close();


    ofstream output("maxflow.out");
    output<<getMaxFlowEdmondsKarp(adjacencyList, numberOfNodes, 0, numberOfNodes - 1);
    output.close();

    return 0;
}