#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:
    vector<vector<int>> capacityMatrix;
    vector<vector<Node>> adjList;

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

        struct QueueEntry {
            Node node;
            int flow;
        };
        std::queue<QueueEntry> bfsQueue;
        bfsQueue.push({s, INF});

        while (!bfsQueue.empty()) {
            auto [node, flow] = bfsQueue.front();
            bfsQueue.pop();

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

                prevInPath[to] = node;
                int newFlow = std::min(flow, capacityMatrix[node][to]);

                if (to == t) {
                    return newFlow;
                }
                bfsQueue.push({to, newFlow});
            }
        }

        return 0;
    }

public:
    explicit FlowNetwork(int 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 maxFlow(Node s, Node t) {
        int maxFlow = 0;
        vector<Node> prevInPath(adjList.size());

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

            Node current = t;
            while (current != s) {
                Node prev = prevInPath[current];
                capacityMatrix[prev][current] -= newFlow;
                capacityMatrix[current][prev] += newFlow;
                current = prev;
            }
        }

        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.maxFlow(1, nodeCount) << '\n';
    fout.close();

    return 0;
}