#ifndef POTTS_NETWORK_HPP
#define POTTS_NETWORK_HPP

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

namespace potts
{

class Network
{
public:
    struct Edge
    {
        std::size_t dst;
        int capacity;
        std::size_t rev_edge;
        
        Edge() = default;
        Edge(const std::size_t dst, const int capacity, const std::size_t rev_edge) : dst(dst), capacity(capacity), rev_edge(rev_edge) {}
    };
    
private:
     std::vector<std::vector<Edge>> edges;
     
public:
    Network() = default;
    Network(const std::size_t n) : edges(n) {}
    
    void clear()
    {
        edges.clear();
    }
    
    void resize(std::size_t n)
    {
        edges.resize(n);
    }
    
    std::size_t num_nodes() const noexcept
    {
        return edges.size();
    }
    
    std::vector<Edge>& operator[](const std::size_t i) noexcept
    {
        assert(i < num_nodes());
        return edges[i];
    }
    
    const std::vector<Edge>& operator[](const std::size_t i) const noexcept
    {
        assert(i < num_nodes());
        return edges[i];
    }
    
    void add_edge(const std::size_t src, const std::size_t dst, const int capacity)
    {
        edges[src].emplace_back(dst, capacity, edges[dst].size());
        edges[dst].emplace_back(src, 0, edges[src].size() - 1);
    }
};

} // end of namespace potts

#endif

#ifndef POTTS_DINIC_HPP
#define POTTS_DINIC_HPP

namespace potts
{

class Dinic
{
private:
    std::vector<int> level;
    std::vector<std::size_t> iter;
    
    void bfs(const Network& network, const std::size_t s);
    int dfs(Network& network, const std::size_t v, const std::size_t t, const int f);
    
public:
    Dinic() = default;
    int compute(Network& network, const std::size_t s, const std::size_t t);
};

} // end of namespace potts

#endif

#include <algorithm>
#include <queue>

namespace potts
{
    
void Dinic::bfs(const Network& network, const std::size_t s)
{
    std::fill(level.begin(), level.end(), -1);
    std::queue<std::size_t> Q;
    level[s] = 0;
    Q.push(s);
    
    while(!Q.empty()){
        const std::size_t v = Q.front();
        Q.pop();
        
        for(const Network::Edge& e : network[v]){
            if(e.capacity > 0 && level[e.dst] < 0){
                level[e.dst] = level[v] + 1;
                Q.push(e.dst);
            }
        }
    }
}

int Dinic::dfs(Network& network, const std::size_t v, const std::size_t t, const int f)
{
    if(v == t){
        return f;
    }
    
    for(std::size_t& i=iter[v]; i < network[v].size(); ++i){
        Network::Edge& e = network[v][i];
        if(e.capacity > 0 && level[v] < level[e.dst]){
            const int d = dfs(network, e.dst, t, std::min(f, e.capacity));
            if(d > 0){
                e.capacity -= d;
                network[e.dst][e.rev_edge].capacity += d;
                return d;
            }
        }
    }
    
    return 0;
}

int Dinic::compute(Network& network, const std::size_t s, const std::size_t t)
{
    level.resize(network.num_nodes());
    iter.resize(network.num_nodes());
    
    std::int64_t flow = 0;
    
    for(;;){
        bfs(network, s);
        if(level[t] < 0){
            return flow;
        }
        std::fill(iter.begin(), iter.end(), 0);
        
        int f;
        while((f = dfs(network, s, t, std::numeric_limits<int>::max())) > 0){
            flow += f;
        }
    }
}

} // end of namespace potts

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=jp

#include <iostream>

int main()
{
    int n, m;
    std::cin >> n >> m;
    
    potts::Network network(n);
    
    for(int i=0; i<m; ++i){
        int u, v, c;
        std::cin >> u >> v >> c;
        network.add_edge(u, v, c);
    }
    
    potts::Dinic dinic;
    std::cout << dinic.compute(network, 0, n-1) << std::endl;
}

Measured memory_bytes: 3244