#include <bits/stdc++.h>

#define fi first
#define sc second
#define pb push_back

using namespace std;
const int inf = 2e9;

int n, m;

struct FLOW {
    struct edge {
        int cap, to;
    };

    vector<int> level, start;
    vector<edge> e;
    vector<vector<int>> g;

    FLOW(int n) {
        e.clear();
        g.clear();
        g.resize(n+5);
        level.resize(n+5, 0);
        start.resize(n+5, 0);
    }
    void add_edge(int cap, int from, int to) {
        g[from].pb(e.size());
        e.pb({cap, to});
        g[to].pb(e.size());
        e.pb({0, from});
    }
    bool bfs(int s, int t) {
        level.assign(level.size(), 0);

        level[s] = 1;
        queue<int> que;
        que.push(s);
        while(!que.empty()) {
            int nod = que.front();
            que.pop();

            for(auto idk : g[nod]) {
                auto [cap, nxt] = e[idk];
                if(cap && !level[nxt]) {
                    level[nxt] = level[nod] + 1;
                    que.push(nxt);
                }
            }

        }

        return level[t] != 0;
    }
    int sendflow(int t, int nod, int flow) {
        if(nod == t)
            return flow;
        else {
            for(; start[nod]<g[nod].size(); start[nod]++) {
                auto [cap, to] = e[g[nod][start[nod]]];
                if(level[nod] + 1 == level[to] && cap) {
                    int nowflow = min(flow, cap);
                    int nxtflow = sendflow(t, to, nowflow);
                    if(nxtflow > 0) {
                        e[g[nod][start[nod]]].cap -= nxtflow;
                        e[g[nod][start[nod]]^1].cap += nxtflow;

                        return nxtflow;
                    }
                }
            }
        }

        return 0;
    }
    int dinic(int s, int t) {
        int ans = 0;
        while(bfs(s, t)) {
            start.assign(start.size(), 0);

            int res;
            while(res = sendflow(t, s, inf))
                ans += res;
        }

        return ans;
    }
};

int main()
{
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    cin.tie(nullptr)->sync_with_stdio(0);

    cin >> n >> m;
    FLOW ew(n);
    for(int i=1; i<=m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        ew.add_edge(z, x, y);
    }

    cout << ew.dinic(1, n);
    return 0;
}