#include <cassert>
#include <cstddef>
#include <list>
#include <vector>

// Base class of flow algorithms
template <class cap_t, class cost_t>
struct flow_base
{
    struct edge_t
    {
        size_t src, dst;
        cap_t cap; cost_t cost;
        edge_t *rev;
        edge_t(size_t _src, size_t _dst, cap_t _cap, cost_t _cost, edge_t *_rev)
            : src(_src), dst(_dst), cap(_cap), cost(_cost), rev(_rev) {}
    }; // struct edge_t

protected:
    using adj_type = std::vector<std::list<edge_t>>;
    adj_type adj;

public:
    flow_base(const size_t _n = 0) : adj(_n) {}

    flow_base(const flow_base& other) : adj(other.size())
    {
        for(size_t node{0}; node != other.size(); ++node)
        {
            for(const auto &e : other[node])
            {
                if(e.src == node)
                {
                    adj[e.src].emplace_back(e);
                    adj[e.dst].emplace_back(*e.rev);
                    adj[e.src].back().rev = &adj[e.dst].back();
                    adj[e.dst].back().rev = &adj[e.src].back();
                    e.rev->src = -1;
                }
                else
                {
                    e.rev->rev->src = node;
                }
            }
        }
    }

    flow_base &operator=(const flow_base &other)
    {
        if(this != &other)
        {
            adj = decltype(adj)(other.size());
            for(size_t node{0}; node != other.size(); ++node)
            {
                for(const auto &e : other[node])
                {
                    if(e.src == node)
                    {
                        adj[e.src].emplace_back(e);
                        adj[e.dst].emplace_back(*e.rev);
                        adj[e.src].back().rev = &adj[e.dst].back();
                        adj[e.dst].back().rev = &adj[e.src].back();
                        e.rev->src = -1;
                    }
                    else
                    {
                        e.rev->rev->src = node;
                    }
                }
            }
        }
        return *this;
    }

    size_t size() const { return adj.size(); }

    typename decltype(adj)::reference operator[](size_t node) { assert(node < size()); return adj[node]; }
    typename decltype(adj)::const_reference operator[](size_t node) const { assert(node < size()); return adj[node]; }

    void add_edge(size_t src, size_t dst, cap_t cap, cost_t cost)
    {
        assert(src < size()); assert(dst < size());
        if(cap <= 0) return;
        adj[src].emplace_back(src, dst, cap, cost, nullptr);
        adj[dst].emplace_back(dst, src, 0, -cost, nullptr);
        adj[src].back().rev = &adj[dst].back();
        adj[dst].back().rev = &adj[src].back();
    }
}; // struct flow_base

#include <queue>

// Computing the maximum flow
// depends on base.hpp
template <class cap_t>
class Dinic : public flow_base<cap_t, cap_t>
{
    using base = flow_base<cap_t, cap_t>;
    using itr_type = typename base::adj_type::value_type::iterator;
    std::vector<size_t> level;
    cap_t max_cap;

    bool bfs(const size_t src, const size_t dst)
    {
        fill(level.begin(), level.end(), -1);
        std::queue<size_t> que; que.emplace(src);
        level[src] = 0;
        while(!que.empty())
        {
            size_t node{que.front()}; que.pop();
            for(const auto &e : base::adj[node])
            {
                if(e.cap > 0 && level[e.dst] == size_t(-1))
                {
                    level[e.dst] = level[node] + 1;
                    que.emplace(e.dst);
                }
            }
        }
        return ~level[dst];
    }

    cap_t dfs(const size_t node, const size_t dst, cap_t bound, std::vector<itr_type> &itr)
    {
        if(node == dst) return bound;
        cap_t flow(0);
        for(itr_type &e{itr[node]}; e != base::adj[node].end(); ++e)
        {
            if(e->cap > 0 && level[node] < level[e->dst])
            {
                cap_t achv = dfs(e->dst, dst, std::min(bound, e->cap), itr);
                e->cap -= achv, e->rev->cap += achv;
                flow += achv, bound -= achv;
                if(bound == 0) break;
            }
        }
        return flow;
    }

public:
    Dinic(const size_t _n = 0) : base::flow_base(_n), level(_n), max_cap(0) {}

    Dinic(const Dinic &other) : base::flow_base(other), level(other.size()), max_cap(0) {}

    Dinic &operator=(const Dinic &other)
    {
        base::operator=(other);
        level = other.level;
        max_cap = other.max_cap;
        return *this;
    }

    void add_edge(size_t src, size_t dst, cap_t cap)
    {
        max_cap = std::max(max_cap, cap);
        base::add_edge(src, dst, cap, 0);
    }

    cap_t max_flow(size_t src, size_t dst)
    {
        assert(src < base::size()); assert(dst < base::size());
        cap_t flow(0);
        std::vector<itr_type> itr(base::size());
        while(bfs(src, dst))
        {
            for(size_t node{0}; node != base::size(); ++node) itr[node] = base::adj[node].begin();
            cap_t resid; while((resid = dfs(src, dst, max_cap, itr)) > 0) flow += resid;
        }
        return flow;
    }

    std::vector<bool> min_cut(size_t src, size_t dst)
    {
        max_flow(src, dst);
        std::vector<bool> res(base::size());
        for(size_t node{0}; node != base::size(); ++node) res[node] = ~level[node];
        return res;
    }
}; // class Dinic


#include <iostream>

main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    using namespace std;

    int n,m; cin>>n>>m;
    Dinic<int> dinic(n);
    while(m--)
    {
        int a,b,c; cin>>a>>b>>c;
        dinic.add_edge(a,b,c);
    }
    cout << dinic.max_flow(0,n-1) << "\n";
}



Measured memory_bytes: 3308