#include <bits/stdc++.h>
using namespace std;

using ll = long long;

class maxflow{
    int n, s, t, mf = 0, minflow, ret = 0;
    struct edge{
        int rev, dest, cap, flow;
    };
    vector<vector<edge>> vec;
    vector<int> dist;

    void bfs(){
        fill(begin(dist), end(dist), n + 10);
        queue<int> q;
        q.push(s);
        dist[s] = 0;

        while(!q.empty()){
            int curr = q.front();
            q.pop();

            for(auto next : vec[curr]){
                if(dist[next.dest] > n && next.cap - next.flow >= minflow){
                    dist[next.dest] = dist[curr] + 1;
                    q.push(next.dest);
                }
            }
        }
    }

    ll dfs(int curr, ll allowed){
        if(curr == t)
            return allowed;

        const int a0 = allowed;

        for(auto& next : vec[curr])
            if(dist[next.dest] == dist[curr] + 1 && next.cap - next.flow >= minflow){
                int here = dfs(next.dest, min<ll>(allowed, next.cap - next.flow));
                next.flow += here;
                vec[next.dest][next.rev].flow -= here;
                allowed -= here;
            }

        return a0 - allowed;
    }

    void do_round(){
        bfs();
        while(dist[t] <= n){
            ret += dfs(s, (ll)n * mf);
            bfs();
        }
    }
public:
    maxflow(int N, int S, int T): n(N), s(S), t(T), vec(n), dist(n){}

    void add_edge(int x, int y, int c){
        vec[x].push_back(edge { (int)vec[y].size(), y, c, 0 });
        vec[y].push_back(edge { (int)vec[x].size() - 1, x, 0, 0 });

        mf = max(mf, c);
    }

    int solve(){
        for(minflow = mf; minflow >= 1; minflow /= 2)
            do_round();

        return ret;
    }
};

int main(){
    ifstream f("maxflow.in");
    ofstream g("maxflow.out");

    int n, m;
    f >> n >> m;

    maxflow mf(n, 0, n - 1);

    for(int i = 0, x, y, c; i < m; ++i){
        f >> x >> y >> c;
        mf.add_edge(x - 1, y - 1, c);
    }

    g << mf.solve() << '\n';
    return 0;
}