#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

class Edge{
public:
    int from, to;
    Int limit;
    Int rev;
    Edge(int from, int to, Int limit = 0, Int rev = 0):
        from(from),to(to),limit(limit), rev(rev){}
};

class Graph{
public:
    int n;
    vector<Edge> edges;
    vector<vector<int>> adj;
    Graph(int n):n(n),adj(n){}

    void add_edge(int from, int to, Int limit){
        Edge e(from, to, limit, edges.size() + 1);
        Edge rev(to, from, 0, edges.size());
        adj[from].push_back(edges.size());
        adj[to].push_back(edges.size() + 1);
        edges.push_back(e);
        edges.push_back(rev);
    }
};

class PushRelabel{
public:
    vector<vector<int>> active;
    vector<vector<int>> admissible;
    vector<Int> ex;
    vector<int> height;
    Graph g;
    int highest;
    PushRelabel(Graph g):g(g), height(g.n), active(2*g.n), ex(g.n), admissible(g.n){}

    Int calc(int s, int t){
        height[s] = g.n;
        for(auto e_ind: g.adj[s]){
            auto &e = g.edges[e_ind];
            if(e.limit == 0)continue;
            flow_edge(e, e.limit);
        }
        highest = 0;

        while(!active[highest].empty()){
            int v = active[highest].back();
            if(v == s || v == t)active[highest].pop_back();
            else if(admissible[v].empty())relabel(v);
            else push(v);
        }
        return ex[t];
    }

    bool is_admissible(Edge &e){
        return e.limit > 0 && height[e.from] - 1 == height[e.to];
    }
    
    void relabel(int v){
        active[highest].pop_back();
        height[v] = 2 * g.n;
        for(auto e_ind:g.adj[v]){
            auto &e = g.edges[e_ind];
            if(e.limit > 0)height[v] = min(height[v], height[e.to] + 1);
        }
        for(auto e_ind:g.adj[v]){
            auto &e = g.edges[e_ind];
            if(is_admissible(e))admissible[v].push_back(e_ind);
        }
        highest = height[v];
        active[highest].push_back(v);
    }

    void push(int v){
        Edge &e = g.edges[admissible[v].back()];
        if(!is_admissible(e)){
            admissible[v].pop_back();
            return; 
        }
        flow_edge(e, min(e.limit, ex[v]));
        if(e.limit == 0){
            admissible[v].pop_back();
        }
        if(ex[v] == 0){
            active[highest].pop_back();
            while(highest > 0 && active[highest].empty())highest--;
        }
    }

    void flow_edge(Edge &e, int f){
        Edge &rev = g.edges[e.rev];
        e.limit -= f;
        ex[e.from] -= f;
        rev.limit += f;
        ex[e.to] += f;
        if(ex[e.to] == f){
            active[height[e.to]].push_back(e.to);
        }
    }
};

int main(){
    int v, e;
    cin >> v >> e;
    Graph g(v);
    for(int i = 0;i < e;i++){
        int u, v, c;
        cin >> u >> v >> c;
        g.add_edge(u, v, c);
    }
    PushRelabel pr(g);

    cout << pr.calc(0, v-1) << endl;

    
    return 0;
}


Measured memory_bytes: 3296