#define ENABLE_DEBUG 0
// hidden common codes{{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(lint ngtkana_is_a_genius=0; ngtkana_is_a_genius<(lint)k; ngtkana_is_a_genius++)
using lint=long long;
using ld=long double;
template<class T> using numr=std::numeric_limits<T>;
struct input_t {
    template<class T> operator T() {
        T t;
        std::cin>>t;
        return t;
    }
} input;
#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

template <class Flow> struct flow_edge {
    std::size_t to, rev;
    Flow cap;

    flow_edge(std::size_t to_, std::size_t rev_, Flow cap_)
        : to(to_), rev(rev_), cap(cap_) {}
};

template <class Flow> std::ostream& operator<< (std::ostream& os, flow_edge<Flow> const& e) {
    return os << '(' << e.to << ',' << e.cap << ')';
}

template <class Flow> struct flow_edges_list {
    std::vector<flow_edge<Flow>> contents;
    std::size_t current;
};

template <class Flow> struct relabel_to_front {
    std::size_t s, t;
    std::vector<flow_edges_list<Flow>> g;
    std::vector<unsigned> h;
    std::vector<Flow> ex;
    std::list<std::size_t> list;

    relabel_to_front(std::size_t n, std::size_t s_, std::size_t t_)
        : s(s_), t(t_), g(n), h(n), ex(n, zero())
    {
        h.at(0) = n;
        for (std::size_t i=0; i<n; i++) if (i!=s && i!=t) {
            list.push_back(i);
        }
    }

    void insert(std::size_t u, std::size_t v, Flow w) {
        std::size_t su = g.at(u).contents.size();
        std::size_t sv = g.at(v).contents.size();
        g.at(u).contents.emplace_back(v, sv, w);
        g.at(v).contents.emplace_back(u, su, 0);
    }

    std::size_t size() const { return g.size(); }

    static Flow zero() { return Flow{ 0 }; }

    void initialize_preflow() {
        for (auto& e : g.at(s).contents) {
            Flow d = e.cap;
            ex.at(s) -= d;
            ex.at(e.to) += d;
            e.cap -= d;
            g.at(e.to).contents.at(e.rev).cap += d;
        }
    }

    void push(std::size_t u, flow_edge<Flow>& e) {
        assert(0<ex.at(u) && zero()<e.cap && h.at(u)==h.at(e.to)+1);

        Flow d=std::min(ex.at(u), e.cap);
        DEBUG("push", u, e.to, d);
        e.cap -= d;
        g.at(e.to).contents.at(e.rev).cap += d;
        ex.at(u) -= d;
        ex.at(e.to) += d;

        DEBUG(matrix_style<6>(to_vec()));
        DEBUG(ex);
        DEBUG(h);
    }

    void relabel(std::size_t u) {
        DEBUG("relabel", u);
        assert(0<ex.at(u));

        unsigned min = 2*size();
        for (flow_edge<Flow> const& e : g.at(u).contents) {
            if (e.cap!=zero()) {
                assert(h.at(u) <= h.at(e.to));
                min = std::min(min, h.at(e.to));
            }
        }
        h.at(u) = min + 1;
    }

    bool discharge(std::size_t u) {
        DEBUG("discharge", u);

        bool relabelled = false;
        std::size_t& c = g.at(u).current;
        for (c=0; ex.at(u); c++) {
            if (c==g.at(u).contents.size()) {
                relabel(u);
                c=0;
                relabelled = true;
            }

            flow_edge<Flow>& e = g.at(u).contents.at(c);
            if (zero()<e.cap && h.at(u)==h.at(e.to)+1) {
                push(u, e);
            }
        }
        return relabelled;
    }

    Flow run() {
        initialize_preflow();

        DEBUG(matrix_style<6>(to_vec()));
        DEBUG(ex);
        DEBUG(h);
        for (auto it=list.begin(); it!=list.end(); it++) {
            if (discharge(*it)) {
                list.push_front(*it);
                list.erase(it);
                it = list.begin();
            }
        }

        return ex.at(t);
    }

    std::vector<std::vector<flow_edge<Flow>>> to_vec() const {
        std::vector<std::vector<flow_edge<Flow>>> ans(size());
        for (std::size_t i=0; i<size(); i++) {
            ans.at(i) = g.at(i).contents;
        }
        return ans;
    }
};

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

    lint n=input,m=input;
    auto rf=relabel_to_front<lint>(n, 0, n-1);
    while (m--) {
        lint u=input,v=input,w=input;
        rf.insert(u, v, w);
    }
    std::cout << rf.run() << '\n';
}



Measured memory_bytes: 3260