//! Dinic のアルゴリズムによりフローネットワークの最大流を求めます．

use std::collections::{HashMap, VecDeque};

/// 流量を表す型です．競技プログラミングでは `num` クレートが使えないことが多いため，
/// やむなく，このようにテンプレート化せずに型エイリアスを使っています．
pub type Flow = i32;

#[derive(Clone)]
struct Edge {
    src: usize,
    dst: usize,
    cap: Flow,
    flow: Flow,
    rev: usize,
    is_rev: bool,
}

#[derive(Default)]
pub struct Dinic {
    n: usize,
    edges: Vec<((usize, usize), Flow)>,
    graph: Vec<Vec<Edge>>,
    src: usize,
    dst: usize,
    level: Vec<u32>,
    prog: Vec<usize>,
    queue: VecDeque<usize>,
}

impl Dinic {
    /// 頂点数を `n` の `Dinic` 構造体を作成します．
    pub fn new(n: usize) -> Self {
        assert!(n >= 2);
        Dinic {
            n: n, ..Default::default()
        }
    }

    /// `src` から `dst` への容量 `cap` の辺を追加します．
    pub fn add_edge(&mut self, src: usize, dst: usize, cap: Flow) {
        assert!(src < self.n);
        assert!(dst < self.n);
        if src != dst && cap != 0 {
            self.edges.push(((src, dst), cap));
        }
    }

    /// `src` から `dst` への最大流を求めます．
    /// 内部で深さ優先探索を行うので，スタックオーバーフローに注意が必要です．
    pub fn maximum_flow(&mut self, src: usize, dst: usize) -> Flow {
        assert!(src < self.n);
        assert!(dst < self.n);
        assert!(src != dst);

        self.src = src;
        self.dst = dst;
        self.make_graph();
        self.queue = VecDeque::new();

        let mut res = 0;
        while self.levelize() {
            self.prog = vec![0; self.n];
            let s = self.src;
            res += self.augument(s, Flow::max_value());
        }
        res
    }
}

impl Dinic {
    /// 今までに `add_edge` に追加された辺からグラフを作ります．
    /// 多少の高速化のために多重辺がまとまられます．
    fn make_graph(&mut self) {
        let n = self.n;
        let mut caps = vec![HashMap::new(); n];
        for &((u, v), f) in self.edges.iter() {
            *caps[u].entry(v).or_insert(0) += f;
        }
        self.graph = vec![vec![]; self.n];
        for u in 0..n {
            for (&v, &c) in caps[u].iter() {
                let iu = self.graph[u].len();
                let iv = self.graph[v].len();
                let uv = Edge {
                    src: u,
                    dst: v,
                    cap: c,
                    flow: 0,
                    rev: iv,
                    is_rev: false,
                };
                let vu = Edge {
                    src: v,
                    dst: u,
                    cap: c,
                    flow: c,
                    rev: iu,
                    is_rev: true,
                };
                self.graph[u].push(uv);
                self.graph[v].push(vu);
            }
        }
    }

    /// 幅優先探索を行い，各頂点のレベルを求めます．
    fn levelize(&mut self) -> bool {
        self.level = vec![0; self.n];
        self.level[self.src] = 1;

        self.queue.clear();
        self.queue.push_back(self.src);

        while let Some(v) = self.queue.pop_front() {
            if v == self.dst {
                break;
            }
            for e in self.graph[v].iter() {
                let residue = e.cap - e.flow;
                if self.level[e.dst] == 0 && residue != 0 {
                    self.level[e.dst] = self.level[v] + 1;
                    self.queue.push_back(e.dst);
                }
            }
        }

        self.level[self.dst] != 0
    }

    /// 深さ優先探索を行い，増加道にフローを流します．
    /// スタックオーバーフローに注意が必要です．
    fn augument(&mut self, v: usize, mut bound: Flow) -> Flow {
        use std::cmp::min;
        if v == self.dst {
            bound
        } else {
            let mut res = 0;
            while self.prog[v] < self.graph[v].len() {
                if bound == 0 {
                    break;
                }

                let mut e = self.graph[v][self.prog[v]].clone();
                let residue = e.cap - e.flow;
                if residue != 0 && self.level[v] < self.level[e.dst] {
                    let aug = self.augument(e.dst, min(bound, residue));
                    e.flow += aug;
                    self.reverse(&e).flow -= aug;
                    res += aug;
                    bound -= aug;
                }
                self.graph[v][self.prog[v]] = e;
                self.prog[v] += 1;
            }
            res
        }
    }

    /// e の逆辺を返します．
    fn reverse(&mut self, e: &Edge) -> &mut Edge {
        &mut self.graph[e.dst][e.rev]
    }
}

// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2756723#1
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let mut dn = Dinic::new(n + 1);
    let m = read();
    for _ in 0..m {
        let (a, b, c) = (read(), read(), read());
        dn.add_edge(a, b, c);
    }
    println!("{}", dn.maximum_flow(0, n - 1));
}



Measured memory_bytes: 5072