#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define loop(i,a,b) for(ll i=(a);i<ll(b);i++)
#define rep(i,b) loop(i,0,b)

typedef int Capacity;
typedef int Weight;
struct Edge {
    int src, dst;
    Capacity cap;
    Edge(int src_, int dst_, Capacity cap_) :
        src(src_), dst(dst_), cap(cap_) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

struct FordFulkerson {
    typedef vector<vector<Capacity>> Matrix;
    int n, t;
    vector<bool> vis;
    vector<vector<Capacity>> cap, flow;
    vector<vector<int>> g;
    Capacity inf;
    FordFulkerson(int n)
        : n(n), cap(n, vector<Capacity>(n)),
          flow(n, vector<Capacity>(n)), g(n, vector<int>()),
          inf(numeric_limits<Capacity>::max()/8){}
    FordFulkerson(const Graph &graph){
        *this = FordFulkerson(graph.size());
        rep(i,n) for(auto &e : graph[i]) addEdge(e.src, e.dst, e.cap);
    }
    void addEdge(int u, int v, Capacity c){
        cap[u][v] += c; cap[v][u] += c; flow[v][u] += c;
        g[u].push_back(v); g[v].push_back(u);
    }
    Capacity solve(int s, int t){
        this->t = t;
        Capacity res = 0, inc = 1;
        while(inc > 0){
            vis.assign(n, false);
            res += (inc = augment(s, inf));
        }
        return res;
    }
    Capacity augment(const int &v, const Capacity &lim){
        vis[v] = true;
        if(v == t) return lim;
        for(const int &i : g[v]){
            if(vis[i] || flow[v][i] == cap[v][i]) continue;
            Capacity f = augment(i, min(lim, cap[v][i] - flow[v][i]));
            flow[v][i] += f;
            flow[i][v] -= f;
            if(f) return f;
        }
        return 0;
    }
};

struct EdmondsKerp {
    int n, t;
    vector<int> prev, dist;
    vector<vector<Capacity>> cap, flow;
    vector<vector<int>> g;
    Capacity inf;
    EdmondsKerp(int n)
        : n(n), cap(n, vector<Capacity>(n)), flow(n, vector<Capacity>(n)),
          g(n, vector<int>()), inf(numeric_limits<Capacity>::max()/8){}
    EdmondsKerp(const Graph &graph){
        *this = EdmondsKerp(graph.size());
        rep(i,n) for(auto &e : graph[i]) addEdge(e.src, e.dst, e.cap);
    }
    void addEdge(int u, int v, Capacity c){
        cap[u][v] += c; cap[v][u] += c; flow[v][u] += c;
        g[u].push_back(v); g[v].push_back(u);
    }
    Capacity solve(int s, int t){
        // show();
        this->t = t;
        Capacity res = 0, inc = 1;
        while(inc > 0){
            prev.assign(n, -1);
            dist.assign(n, inf);
            dist[s] = 0;
            res += (inc = augment(s,t));
            // show();
        }
        return res;
    }
    Capacity augment(int s, int t){
        queue<pair<int,Capacity>> q;
        q.emplace(s,inf);
        Capacity aug = 0;
        while(q.size()){
            int v; Capacity f;
            tie(v,f) = q.front(); q.pop();
            if(v == t){
                aug = f; break;
            }
            for(const int& d : g[v]){
                // printf(" %d %d %d %d\n", v, d, dist[v], dist[d]);
                if(dist[d] <= dist[v] + 1) continue;
                if(cap[v][d] - flow[v][d] == 0) continue;
                dist[d] = dist[v] + 1;
                prev[d] = v;
                // printf("%d %d %d %d\n", v, d, cap[v][d], flow[v][d]);
                q.emplace(d, min(f, cap[v][d] - flow[v][d]));
            }
        }
        if(aug == 0) return 0;
        int cur = t;
        vector<int> path = {cur};
        while(cur != s){
            int pre = prev[cur];
            flow[pre][cur] += aug;
            flow[cur][pre] -= aug;
            cur = pre;
            path.push_back(cur);
        }
        // reverse(path.begin(), path.end());
        // for(auto & v : path) cout << v << " ";
        // cout << endl;
        // cout << aug << endl;
        return aug;
    }
    void show(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                Capacity f = flow[i][j];
                if(f > 0) printf("%d -> %d (%d)\n", i,j,f);
            }
        }
        puts("");
    }
};

// Graph generate(int n, int m){
//     Graph g(n);
//     rep(i,m){
//         int a = 0, b = 0;
//         while(a == b){
//             a = rand()%n, b = rand()%n;
//         }
//         int c = rand()%3;
//         g[a].emplace_back(a,b,c);
//     }
//     return g;
// }

// Graph chal1(){
//     Graph g(4);
//     g[0].emplace_back(0,2,2);
//     g[0].emplace_back(0,1,1);
//     g[0].emplace_back(0,1,1);
//     g[1].emplace_back(1,3,1);
//     g[2].emplace_back(2,3,2);
//     g[3].emplace_back(3,2,0);
//     g[3].emplace_back(3,0,2);
//     g[3].emplace_back(3,2,1);
//     return g;
// }

// int main(){
//     Graph g = chal1();
//     int n = 4, m = 8;
//     int f1 = FordFulkerson(g).solve(0,n-1);
//     int f2 = EdmondsKerp(g).solve(0,n-1);
//     if(f1 != f2){
//         cout << f1 << " " << f2 << endl;
//     }
// }

int main(){
    int N,M;
    cin >> N >> M;
    Graph g(N);
    rep(i,M){
        int a,b,c;
        cin >> a >> b >> c;
        g[a].emplace_back(a,b,c);
    }
    EdmondsKerp ek(g);
    cout << ek.solve(0,N-1) << endl;
}

Measured memory_bytes: 1352