#include <bits/stdc++.h>

#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) int((x).size())

using namespace std;

mt19937 gen_rand;

/*OUTPUT*/
/*PAIR*/
template<typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &a) {
    os << "(";
    os << a.first << ", ";
    os << a.second;
    os << ")";
    return os;
}
/*PAIR*/

/*ARR*/
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    os << "{";
    bool was = false;
    for (auto &x: a) {
        if (was) {
            os << ", ";
        }
        was = true;
        os << x;
    }
    os << "}";
    return os;
}
/*ARR*/
/*OUTPUT*/

/*DEBUG*/
template<typename T>
inline void debug(const char* sdbg, T x) {
    cerr << "The value of " << sdbg << " is " << x << "\n";
};

template<typename T, typename... U>
inline void debug(const char* sdbg, T h, U... t) {
    cerr << "The value of ";
    while (*sdbg != ',') {
        cerr << *sdbg++;
    }
    cerr << " is " << h << "\n";
    debug(sdbg + 1, t...);
    cerr << "\n";
}

#define value(...) debug(#__VA_ARGS__, __VA_ARGS__)
/*DEBUG*/

template<typename T>
T abs(T x) {
    if (x < 0) {
        return -x;
    } else {
        return x;
    }
}

template<typename T>
T sqr(T x) {
    return x * x;
};

const long long INF_FOR_SHORT_TIME = (long long)(1e9);

template<typename T>
T mul(T a, T b, T m) {
    if (a <= INF_FOR_SHORT_TIME && b <= INF_FOR_SHORT_TIME) {
        return (a * b) % m;
    }
    T q = (long long)((long double)a * (long double)b / (long double)m);
    T r = a * b - q * m;
    return (r + 5 * m) % m;
}

template<typename T, typename U>
T binpow(T a, U n, T MOD) {
    T res = 1;
    while (n) {
        if (n & 1) {
            res = mul(res, a, MOD);
        }
        a = mul(a, a, MOD);
        n >>= 1;
    }
    return res;
};

template<typename T>
int sign(T x) {
    if (x < 0) {
        return -1;
    } else if (x > 0) {
        return 1;
    } else {
        return 0;
    }
};

template<typename T>
T gcd(T a, T b) {
    if (a > b) {
        swap(a, b);
    }
    while (a) {
        b %= a;
        swap(a, b);
    }
    return b;
};

template<typename T>
bool uin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
};

template<typename T>
bool uax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
};

typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

/*curlink v1.7*/

const ll INF = ll(1e9) + 7;

struct edge {
    ll u, c, f;
    edge *r;

    edge() :
        u(-1),
        c(0),
        f(0),
        r(nullptr) {}

    edge(ll u, ll c, ll f) :
        u(u),
        c(c),
        f(f),
        r(nullptr) {}
};

ll n, m, s, t;
vector<vector<edge*>> g;
vector<ll> ptr, dist;

void add(ll v, ll u, ll cap) {
    g[v].push_back(new edge(u, cap, 0));
    g[u].push_back(new edge(v, 0, 0));
    g[v].back()->r = g[u].back();
    g[u].back()->r = g[v].back();
}

void read() {
    cin >> n >> m;
    g.resize(n);
    ptr.resize(n, -1);
    dist.resize(n, -1);
    for (ll i = 0; i < m; ++i) {
        ll u, v, cap;
        cin >> u >> v >> cap;
        --u; --v;
        add(u, v, cap);
    }
    s = 0;
    t = n - 1;
}

bool bfs(ll x) {
    for (ll v = 0; v < n; ++v) {
        dist[v] = INF;
        ptr[v] = 0;
    }
    queue<ll> qr;
    qr.push(s);
    dist[s] = 0;
    while (!qr.empty()) {
        ll v = qr.front();
        qr.pop();
        for (auto e : g[v]) {
            if (e->c - e->f >= x && dist[e->u] == INF) {
                dist[e->u] = dist[v] + 1;
                qr.push(e->u);
            }
        }
    }
    return dist[t] != INF;
}

ll dfs(ll v, ll flow, ll x) {
    if (!flow || v == t) {
        return flow;
    }
    for (; ptr[v] < sz(g[v]); ++ptr[v]) {
        auto e = g[v][ptr[v]];
        if (dist[v] + 1 != dist[e->u] || e->c - e->f < x) {
            continue;
        }
        ll cur = dfs(e->u, min(flow, e->c - e->f), x);
        if (cur) {
            e->f += cur;
            e->r->f -= cur;
            return cur;
        }
    }
    return 0;
}

ll dinic() {
    ll flow = 0;
    for (ll x = INF; x > 0; x /= 2) {
        while (bfs(x)) {
            ll pushed = dfs(s, INF, x);
            while (pushed) {
                flow += pushed;
                pushed = dfs(s, INF, x);
            }
        }
    }
    return flow;
}

int main() {
    gen_rand.seed(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    read();
    cout << dinic();
    return 0;
}