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

using namespace std;

class Dinic {
public:
    Dinic(int _nodes, int _source, int _sink) {
        source = _source;
        sink = _sink;
        nodes = _nodes;
        last.resize(nodes, 0);
        level.resize(nodes, 0);
        graph.resize(nodes, vector <pair <int, int>>());
    }
    void AddEdge(int _u, int _v, int _cap) {
        graph[_u].push_back(make_pair(_v, edges.size()));
        edges.push_back({ _u, _v, 0, _cap });
        graph[_v].push_back(make_pair(_u, edges.size()));
        edges.push_back({ _u, _v, 0, 0 });
    }
    int MaxFlow() {
        int maxFlow = 0;
        while (bfs()) {
            last.clear();
            last.resize(nodes, 0);
            int deltaFlow = dfs(source, INF);
            while (deltaFlow > 0) {
                maxFlow += deltaFlow;
                deltaFlow = dfs(source, INF);
            }
        }
        return maxFlow;
    }
private:
    const int INF = (1 << 30);
    struct Edge {
        int u, v, flow, cap;
    };
    int source, sink, nodes;
    vector <int> last, level;
    vector <Edge> edges;
    vector <vector <pair <int, int>>> graph;
    bool bfs() {
        level.clear();
        level.resize(nodes, INF);
        level[source] = 0;
        queue <int> q;
        q.push(source);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            if (node == sink)
                continue;
            for (auto& x : graph[node]) {
                int flow = edges[x.second].flow;
                int cap = edges[x.second].cap;
                if (level[x.first] > level[node] + 1 && flow < cap) {
                    level[x.first] = level[node] + 1;
                    q.push(x.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 ind = graph[node][p].second;
                int nextNode = graph[node][p].first;
                int flow = edges[ind].flow;
                int cap = edges[ind].cap;
                if (level[nextNode] == level[node] + 1 && flow < cap) {
                    int currFlow = dfs(nextNode, min(deltaFlow, cap - flow));
                    if (currFlow > 0) {
                        edges[ind].flow += currFlow;
                        edges[ind ^ 1].flow -= currFlow;
                        return currFlow;
                    }
                }
            }
            return 0;
        }
    }
    
};

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 = 1; i <= M; ++i) {
        int u, v, cap;
        fin >> u >> v >> cap;
        --u; --v;
        flow.AddEdge(u, v, cap);
    }
    fout << flow.MaxFlow() << "\n";
    fin.close();
    fout.close();
    return 0;
}