#include <fstream>
#include <limits>
#include <queue>
#include <vector>

using std::vector;
using Node = int;

const int INF = std::numeric_limits<int>::max();

class FlowNetwork {
private:
    int nodeCount;
    vector<vector<int>> capacityMatrix;
    vector<vector<Node>> adjList;

    void buildBfsTree(Node s, Node t, vector<Node> &prevInTree) {
        std::fill(prevInTree.begin(), prevInTree.end(), -1);
        prevInTree[s] = -2;

        std::queue<Node> bfsQueue;
        bfsQueue.push(s);

        while (!bfsQueue.empty()) {
            auto node = bfsQueue.front();
            bfsQueue.pop();

            for (Node next: adjList[node]) {
                // Skip visited nodes and saturated edges
                if (prevInTree[next] != -1 || capacityMatrix[node][next] == 0)
                    continue;

                if (next == t)
                    continue;

                prevInTree[next] = node;
                bfsQueue.push(next);
            }
        }
    }

    /// Find the minimum capacity through the path from start to end
    int findMinFlowThroughPath(Node start, Node end, vector<Node> &prevInPath) {
        int flow = INF;
        Node current = end;
        while (current != start) {
            Node prevNode = prevInPath[current];
            flow = std::min(flow, capacityMatrix[prevNode][current]);
            current = prevNode;
        }

        return flow;
    }

    /// Update the flows through the path from start to end with the given value
    void updateFlowThroughPath(Node start, Node end, vector<Node> &prevInPath, int flow) {
        Node current = end;
        while (current != start) {
            Node prev = prevInPath[current];
            capacityMatrix[prev][current] -= flow;
            capacityMatrix[current][prev] += flow;
            current = prev;
        }

    }

    /// Try to find an augmenting path and return the added flow
    int tryAugmentFlow(Node s, Node t, vector<Node> &prevInTree) {
        buildBfsTree(s, t, prevInTree);

        int totalAugmentingFlow = 0;

        // For each node just before t, join it with t and use that as an augmenting path
        for (Node nodeBeforeT: adjList[t]) {
            // Skip node if it was unreachable due to saturation
            if (prevInTree[nodeBeforeT] == -1)
                continue;

            // Join nodeBeforeT and t and update the capacities through the path
            prevInTree[t] = nodeBeforeT;
            auto minFlowThroughPath = findMinFlowThroughPath(s, t, prevInTree);
            updateFlowThroughPath(s, t, prevInTree, minFlowThroughPath);

            totalAugmentingFlow += minFlowThroughPath;
        }

        return totalAugmentingFlow;
    }

public:
    explicit FlowNetwork(int nodeCount) : nodeCount(nodeCount) {
        capacityMatrix.resize(nodeCount, vector<int>(nodeCount));
        adjList.resize(nodeCount);
    }

    void addEdge(Node from, Node to, int capacity) {
        adjList[from].push_back(to);
        adjList[to].push_back(from);
        capacityMatrix[from][to] = capacity;
    }

    int computeMaxFlow(Node s, Node t) {
        int maxFlow = 0;
        vector<Node> prevInPath(nodeCount);

        int newFlow;
        while ((newFlow = tryAugmentFlow(s, t, prevInPath)) > 0) {
            maxFlow += newFlow;
        }

        return maxFlow;
    }
};

int main() {
    std::ifstream fin("maxflow.in");

    int nodeCount, edgeCount;
    fin >> nodeCount >> edgeCount;

    FlowNetwork network(nodeCount + 1);

    for (int i = 0; i < edgeCount; ++i) {
        Node from, to;
        int cap;
        fin >> from >> to >> cap;
        network.addEdge(from, to, cap);
    }

    fin.close();

    std::ofstream fout("maxflow.out");
    fout << network.computeMaxFlow(1, nodeCount) << '\n';
    fout.close();

    return 0;
}