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

using namespace std;

class Dinic {
private:
    struct Edge {
        int from, to, flow, cap;
    };
    int nodes, source, sink;
    const int INF = (1 << 30);
    vector <int> last, level;
    vector <Edge> edges;
    vector <vector <pair <int, int>>> graph;
    bool bfs() {
        fill(level.begin(), level.end(), INF);
        level[source] = 0;
        queue <int> q;
        q.push(source);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (auto& it : graph[node]) {
                int flow = edges[it.second].flow;
                int cap = edges[it.second].cap;
                if (flow < cap && level[it.first] > level[node] + 1) {
                    level[it.first] = level[node] + 1;
                    q.push(it.first);
                }
            }
        }
        return (level[sink] != INF);
    }
    int dfs(int node, int deltaFlow) {
        if (node == sink || deltaFlow == 0) {
            return deltaFlow;
        }
        else {
            for (int& p = last[node]; p < graph[node].size(); ++p) {
                int nextNode = graph[node][p].first;
                int edgeId = graph[node][p].second;
                int flow = edges[edgeId].flow;
                int cap = edges[edgeId].cap;
                if (level[nextNode] == level[node] + 1 && flow < cap) {
                    int pushed = dfs(nextNode, min(deltaFlow, cap - flow));
                    if (pushed) {
                        edges[edgeId].flow += pushed;
                        edges[edgeId ^ 1].flow -= pushed;
                        return pushed;
                    }
                }
            }
            return 0;
        }
    }
    
public:
    Dinic(int _nodes, int _source, int _sink) {
        nodes = _nodes;
        source = _source;
        sink = _sink;
        last.resize(nodes, 0);
        level.resize(nodes, 0);
        graph.resize(nodes, vector <pair <int, int>>());
    }
    void addEdge(int from, int to, int cap) {
        Edge forward = { from, to, 0, cap };
        Edge backward = { to, from, 0, 0 };
        graph[from].push_back({ to, edges.size() });
        edges.push_back(forward);
        graph[to].push_back({ from, edges.size() });
        edges.push_back(backward);
    }
    int maxFlow() {
        int flow = 0;
        while (bfs()) {
            fill(last.begin(), last.end(), 0);
            int deltaFlow = dfs(source, INF);
            while (deltaFlow > 0) {
                flow += deltaFlow;
                deltaFlow = dfs(source, INF);
            }
        }
        return flow;
    }
    
};

int main() {
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    int N, M;
    fin >> N >> M;
    Dinic flow(N, 0, N - 1);
    for (int i = 0; i < M; ++i) {
        int u, v, cap;
        fin >> u >> v >> cap;
        flow.addEdge(u - 1, v - 1, cap);
    }
    fout << flow.maxFlow() << endl;
    fin.close();
    fout.close();
    return 0;
}