pub trait Property: Copy {}

impl<P> Property for P where P: Copy {}

pub trait ZeroP {
    fn zero() -> Self;
}

impl ZeroP for usize { fn zero() -> Self { 0 } }
impl ZeroP for u8 { fn zero() -> Self { 0 } }
impl ZeroP for u16 { fn zero() -> Self { 0 } }
impl ZeroP for u32 { fn zero() -> Self { 0 } }
impl ZeroP for u64 { fn zero() -> Self { 0 } }
impl ZeroP for isize { fn zero() -> Self { 0 } }
impl ZeroP for i8 { fn zero() -> Self { 0 } }
impl ZeroP for i16 { fn zero() -> Self { 0 } }
impl ZeroP for i32 { fn zero() -> Self { 0 } }
impl ZeroP for i64 { fn zero() -> Self { 0 } }

pub trait Weighted: Property + std::ops::Add<Output=Self> + std::cmp::Ord + ZeroP {}

impl<W> Weighted for W where W: Property + std::ops::Add<Output=W> + std::cmp::Ord + ZeroP {}

pub trait NonNegativeWeighted: Weighted {}

impl NonNegativeWeighted for usize {}

pub trait Capacity: Weighted + std::ops::Sub<Output=Self>{}

impl Capacity for usize {}

pub trait Cost: Capacity + std::ops::Mul<Output=Self> {}

#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Vite(pub usize);

#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Eite(pub usize);

pub trait Edge {
    fn from(&self) -> Vite;
    fn to(&self) -> Vite;
}

pub trait Vertex {
    fn new(id : usize) -> Self;
    fn id(&self) -> usize;
}

pub trait Graph<'a, V: Vertex, E: Edge> {
    type EsIter: std::iter::Iterator<Item=&'a Eite>;
    fn add_edge(&mut self, e: E);
    fn delta(&'a self, v: &Vite) -> Self::EsIter;
    fn edge(&self, e: &Eite) -> &E;
    fn vertex(&self, v: &Vite) -> &V;
    fn v_size(&self) -> usize;
    fn e_size(&self) -> usize;
}

pub fn from<E: Edge>(f: Vite, e: &E) -> Vite {
    if e.from() == f { e.from() }
    else { e.to() }
}

pub fn to<E: Edge>(f: Vite, e: &E) -> Vite {
    if e.from() == f { e.to() }
    else { e.from() }
}

pub trait Directed<'a,V: Vertex, E: Edge>: Graph<'a,V,E> {  }
pub trait Undirected<'a,V: Vertex, E: Edge>: Graph<'a,V,E> {  }

pub struct DirectedGraph<V: Vertex, E: Edge> {
    n: usize,
    m: usize,
    g: Vec<Vec<Eite>>,
    es: Vec<E>,
    vs: Vec<V>
}

impl<'a,V: Vertex, E: Edge> Graph<'a,V,E> for DirectedGraph<V,E> {
    type EsIter = std::slice::Iter<'a,Eite>;
    fn add_edge(&mut self, e: E) {
        let ei = Eite(self.m);
        self.m += 1;
        self.g[e.from().0].push(ei);
        self.es.push(e);
    }
    fn delta(&'a self, v: &Vite) -> Self::EsIter {
        self.g[v.0].iter()
    }
    fn edge(&self, e: &Eite) -> &E {
        &self.es[e.0]
    }
    fn vertex(&self, v: &Vite) -> &V {
       &self.vs[v.0]
    }
    fn v_size(&self) -> usize {
        self.n
    }
    fn e_size(&self) -> usize {
        self.m
    }
}

impl<'a,V: Vertex, E: Edge> Directed<'a,V,E> for DirectedGraph<V,E> {  }

impl<V: Vertex, E: Edge> DirectedGraph<V,E> {
    pub fn new(n: usize) -> Self {
        let mut g = DirectedGraph {
            n: n,
            m: 0,
            g: vec![Vec::<Eite>::new(); n],
            es: Vec::<E>::new(),
            vs: Vec::<V>::new()
        };
        for i in 0..n {
            g.vs.push(V::new(i));
        }
        g
    }
}



pub struct MFlowV {
    pub i: usize
}

impl Vertex for MFlowV {
    fn new(id: usize) -> Self {
        MFlowV { i: id }
    }
    fn id(&self) -> usize {
        self.i
    }
}

pub struct MFlowE {
    pub from: Vite,
    pub to: Vite,
    pub rev: Eite
}

impl Edge for MFlowE {
    fn from(&self) -> Vite { self.from }
    fn to(&self) -> Vite { self.to }
}

pub struct MFlowNetWork<C: Capacity> {
    pub cap: Vec<C>,
    pub g: DirectedGraph<MFlowV,MFlowE>,
    pub source: Vite,
    pub shink: Vite,
    pub max_flow: C
}

impl<C: Capacity> MFlowNetWork<C> {
    pub fn build<V,E,CF>(gg: &DirectedGraph<V,E>, s: Vite, t: Vite, capf: CF) -> MFlowNetWork<C>
        where V: Vertex, E: Edge, CF: Fn(&E) -> C {
            let mut g = DirectedGraph::<MFlowV,MFlowE>::new(gg.v_size());
            let mut cap = Vec::<C>::new();
            for i in 0..gg.v_size() {
                for ei in gg.delta(&Vite(i)) {
                    let e = gg.edge(ei);
                    let from = Vite(i);
                    let to = to(Vite(i), e);
                    let m = g.e_size();
                    g.add_edge(MFlowE{ from: from, to: to, rev: Eite(m + 1) });
                    cap.push(capf(e));
                    g.add_edge(MFlowE{ from: to, to: from, rev: Eite(m) });
                    cap.push(C::zero());
                }
            }
            MFlowNetWork {
                cap: cap,
                g: g,
                source: s,
                shink: t,
                max_flow: C::zero()
            }
        }
}

use std::cmp::min;
use std::collections::vec_deque::*;

fn g_level<C: Capacity>(g: &DirectedGraph<MFlowV,MFlowE>, s: &Vite, cap: &mut Vec<C>) -> Vec<i32> {
    let mut level = vec![-1;g.v_size()];

    let mut que = VecDeque::<Vite>::new();
    que.push_back(s.clone());
    level[s.0] = 0;
    while let Some(v) = que.pop_front() {
        for e in g.delta(&v) {
            let to = to(v,g.edge(e));
            if cap[e.0] > C::zero() && level[to.0] == -1{
                level[to.0] = level[v.0] + 1;
                que.push_back(to.clone());
            }
        }
    }
    level
}

fn dinic_dfs<C: Capacity>(g: &DirectedGraph<MFlowV,MFlowE>, v: &Vite, t: &Vite,cap: &mut Vec<C>, level: &Vec<i32>, f: C) -> C {
    if v == t { f }
    else {
        let mut now = f;
        for e in g.delta(v) {
            let ee = g.edge(e);
            let to = to(*v,ee);
            let rev = ee.rev;
            if cap[e.0] > C::zero() && level[to.0] > level[v.0] {
                let c = min(now, cap[e.0]);
                let d = dinic_dfs(g,&to,t,cap,level,c);
                cap[e.0] = cap[e.0] - d;
                cap[rev.0] = cap[rev.0] + d;
                now = now - d;
            }
        }
        now = f - now;
        now
    }
}

pub fn dinic<C: Capacity>(net: &mut MFlowNetWork<C>) -> C {
    let ref mut cap = &mut net.cap;
    let ref g = & net.g;
    let s = net.source;
    let t = net.shink;
    let mut ans = C::zero();
    let mut inf = C::zero();
    for e in g.delta(&s) {
        inf = inf + cap[e.0];
    }
    loop {
        let level = g_level(g, &s, cap);
        if level[net.shink.0] >= 0 {
            loop {
                let f = dinic_dfs(&g, &s, &t,cap,&level, inf);
                if f > C::zero() {
                    ans = ans + f;
                }
                else {
                    break;
                }
            }
        }
        else {
            break;
        }
    }
    ans
}

struct Ver {
    i: usize
}
 
impl Vertex for Ver {
    fn new(id: usize) -> Self {
        Ver {
            i: id
        }
    }
    fn id(&self) -> usize { self.i }
}
 
struct WEdge {
    from: Vite,
    to: Vite,
    dist: usize
}
 
impl Edge for WEdge {
    fn from(&self) -> Vite { self.from } 
    fn to(&self) -> Vite { self.to }
}
  

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let v:Vec<usize> = s.trim().split_whitespace()
        .map(|e|e.parse().unwrap()).collect();
    let (n,m) = (v[0] , v[1]);
    let mut g = DirectedGraph::<Ver,WEdge>::new(n);
  
    for _ in 0..m {
        let mut t = String::new();
        std::io::stdin().read_line(&mut t).unwrap();
        let a:Vec<usize> = t.trim().split_whitespace()
            .map(|e|e.parse().unwrap()).collect();
        let (x,y,w) = (a[0],a[1],a[2]);
        g.add_edge(WEdge{ from: Vite(x), to: Vite(y), dist: w });
    }
  
    let mut net = MFlowNetWork::<usize>::build(&g,Vite(0),Vite(n - 1),|e| e.dist);
    println!("{}", dinic(&mut net));
}



Measured memory_bytes: 5048