// Dinic O(V^2 * E)
#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
 
ifstream in("maxflow.in");
ofstream out("maxflow.out");
 
struct Edge {
    int from;
    int to;
    ll cap;
    ll flow;
 
    Edge(int x, int y, ll c) : from(x), to(y), cap(c), flow(0) {}
 
    ll resCap() {
        return cap - flow; // residual capacity
    }
};
 
struct DinicMaxFlow {
    const ll inf = 1e18;
    bool isDirected;
    int source;
    int sink;
    vector<Edge> edges;
    vector<vector<int> > v;
    vector<int> level;
    vector<int> lst;
    int N;
    int M;
 
    DinicMaxFlow(bool dir, int s, int d, int n) : isDirected(dir), source(s), sink(d), v(n), level(n), lst(n), N(n), M(0) {}
 
    void addEdge(int from, int to, int cap) {
        /*
            Pentru un graf neorientat si o muchie x y cap putem apela:
                addEdge(x, y, cap)
        */
        edges.push_back(Edge(from, to, cap));
        edges.push_back(Edge(to, from, (isDirected ? 0 : cap)));
        v[from].push_back(M++);
        v[to].push_back(M++);
    }
 
    // the layered network has no cycles obv
    bool canPush() {
        queue<int> q;
        fill(level.begin(), level.end(), -1);
        
        level[source] = 0;
        q.push(source);
 
        while (!q.empty()) {
            int node = q.front();
            q.pop();
 
            if (node == sink) {
                return true;
            }
 
            for (auto edgeId : v[node]) {
                int nxt = edges[edgeId].to;
 
                if (level[nxt] == -1) {
                    if (edges[edgeId].resCap() > 0) {
                        level[nxt] = level[node] + 1;
                        q.push(nxt);
                    }
                }
            }
        }
        
        return false;
    }
 
    ll push(int node, ll pushedFlow) {
        if (pushedFlow == 0) {
            return 0;
        }
 
        if (node == sink) {
            return pushedFlow;
        }
 
        for (; lst[node] < (int) v[node].size(); lst[node]++) { // nu trecem printr-o muchie de mai multe ori
            int edgeId = v[node][lst[node]];
            int nxt = edges[edgeId].to;
            auto resCap = edges[edgeId].resCap();
 
            if (level[node] + 1 != level[nxt] || resCap <= 0) {
                continue;
            }
 
            auto flow = push(nxt, min(pushedFlow, resCap));
            if (flow == 0) {
                continue;
            }
 
            edges[edgeId].flow += flow;
            edges[edgeId ^ 1].flow -= flow;
            
            return flow;
        }
 
        return 0;
    }   
 
    ll maxFlow() {
        ll flow = 0;
        while (canPush()) {
            fill(lst.begin(), lst.end(), 0);
 
            while (auto pushedFlow = push(source, inf)) {
                flow += pushedFlow;
            }
        }
 
        return flow;
    }
};
 
int main() {
    int n, m;
    in >> n >> m;
    DinicMaxFlow graph(true, 0, n - 1, n);
 
    for (int i = 0, x, y, c; i < m; i++) {
        in >> x >> y >> c;
        x--;
        y--;
        graph.addEdge(x, y, c);
    }
 
    out << graph.maxFlow();
 
    return 0;
}