/// `Property` trait is for properties of edges.
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 } }

/// `Weighted` trait is for properties of edges such as distance,cost and so on.
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 {}

/// `NonNegativeWeighted` trait is for algorithm such Dijkstra's Algorithm.
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> {}  
  
/// Vertex object for graphs. it has the index of the vertex.
#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Vertex(pub usize);
  
/// Edge object for graphs.
#[derive(Clone,Copy,Debug)]
pub struct Edge {
    /// index of the edge for edge property.
    pub index : usize,
    /// start vertex of the edge.
    pub from : Vertex,
    /// end vertex of the edge.
    pub to : Vertex
}
  
  
impl PartialEq for Edge {
    fn eq(&self, other: &Self) -> bool {
        self.index == other.index
    }
}
  
impl Eq for Edge {}
  
pub trait Graph<'a,VP: Property,EP: Property> {
    type EIter: std::iter::Iterator<Item=&'a Edge>;
      
    /// this method return the count of vertices of graph.
    fn vertices_cnt(&self) -> usize;
    /// this method return the count of edges of graph.
    fn edges_cnt(&self) -> usize;
    /// this method add new edge to graph.
    fn add_edge(&mut self , from : &Vertex , to : &Vertex , edge_prop : EP);
    /// this method return mutable reference of v's property.
    fn vprop_mut(&mut self, v : &Vertex) -> &mut VP;
    /// this method return reference of v's property.
    fn vprop(&self, v : &Vertex) -> &VP;
    /// this method return mutable reference of e's property.
    fn eprop_mut(&mut self, e : &Edge) -> &mut EP;
    /// this method return reference of e's property.
    fn eprop(&self, e : &Edge) -> &EP;
  
    fn delta(&'a self , v : &Vertex) -> Self::EIter;
}
  
pub trait StaticGraph<'a,VP: Property, EP: Property>: Graph<'a,VP,EP> {
    /// this method create new graph object.
    /// n ... count of vertices.
    /// vp_init ... initial property of vertices.
    fn new(n : usize , vp_init : VP) -> Self;
}
pub trait DynamicGraph<'a,VP: Property, EP: Property>: Graph<'a,VP,EP> {
    fn new() -> Self;
    fn add_vertex(&'a mut self, v: &Vertex,vp: VP) -> bool;
    fn erase_vertex(&'a mut self,v: &Vertex) -> bool;
    fn erase_edge(&'a mut self, e: &Edge) -> bool;
}
  
pub trait Directed<'a,VP: Property,EP: Property>: Graph<'a,VP,EP>{
}
pub trait Undirected<'a,VP: Property,EP: Property>: Graph<'a,VP,EP>{
}
  
pub trait Bipartite<'a,VP: Property,EP: Property>: Undirected<'a,VP,EP> {
    fn binew(left: usize, right: usize, vp_init: VP) -> Self;
    fn left_cnt(&self) -> usize;
    fn right_cnt(&self)-> usize; 
    fn left_vertices(&self) -> std::slice::Iter<Vertex>;
    fn right_vertices(&self) -> std::slice::Iter<Vertex>;
}
  
  
/// struct for Directed Graph.
pub struct DirectedGraph<VP: Property,EP: Property> {
    n : usize,
    m : usize,
    g : Vec<Vec<Edge>>,
    es : Vec<EP>,
    vs : Vec<VP>
}
  
impl<'a,VP : Property ,EP : Property> Graph<'a,VP,EP> for DirectedGraph<VP,EP> {
    type EIter = std::slice::Iter<'a,Edge>;
      
    fn add_edge(&mut self , from : &Vertex , to : &Vertex , edge_prop : EP) {
        self.g[from.0].push(Edge{index : self.m, from : from.clone() , to : to.clone()});
        self.es.push(edge_prop);
        self.m += 1;
    }
    fn vertices_cnt(&self) -> usize { self.n }
    fn edges_cnt(&self) -> usize { self.m }
    fn vprop_mut(&mut self, v : &Vertex) -> &mut VP {
        &mut self.vs[v.0]
    }
    fn vprop(&self, v : &Vertex) -> &VP {
        & self.vs[v.0]
    }
    fn eprop_mut(&mut self, e : &Edge) -> &mut EP {
        &mut self.es[e.index]
    }
    fn eprop(&self, e : &Edge) -> &EP {
        & self.es[e.index]
    }
  
    fn delta(&'a self , v : &Vertex) -> Self::EIter {
        self.g[v.0].iter()
    }
}
  
impl<'a,VP : Property ,EP : Property> StaticGraph<'a,VP,EP> for DirectedGraph<VP,EP> {
    fn new(n : usize , vp_init: VP) -> Self {
        DirectedGraph {
            n: n,
            m: 0,
            g: vec![Vec::<Edge>::new(); n],
            es: Vec::<EP>::new(),
            vs: vec![vp_init; n]
        }
    }
}
  
impl<'a,VP: Property, EP: Property> Directed<'a,VP,EP> for DirectedGraph<VP,EP> {
}
  
pub struct Network<C: Capacity> {
    pub cap: Vec<C>,
    pub g: DirectedGraph<usize,Edge>,
    pub source: Vertex,
    pub shink: Vertex,
    pub max_flow: C
}

impl<C: Capacity> Network<C> {
    pub fn build<VP: Property, EP: Property, F>(gg: &DirectedGraph<VP,EP>,s: Vertex, t: Vertex,cap_sel: F) -> Network<C>
    where F: Fn(&EP) -> C {
        let mut g = DirectedGraph::<usize,Edge>::new(gg.vertices_cnt(),0);
        let mut cap = Vec::<C>::new();

        for i in 0..gg.vertices_cnt() {
            for e in gg.delta(&Vertex(i)) {
                let m = g.edges_cnt();
                g.add_edge(&e.from, &e.to, Edge {from: e.to, to: e.from, index: m + 1});
                cap.push(cap_sel(gg.eprop(e)));
                g.add_edge(&e.to, &e.from, Edge {from: e.from, to: e.to, index: m});
                cap.push(C::zero());
            }
        }

        Network {
            cap: cap,
            g: g,
            source: s,
            shink: t,
            max_flow: C::zero()
        }
    }
}
 
use std::cmp::min;
use std::cmp::max;

pub fn fujishige(net: &mut Network<usize>) -> usize {
    let ref mut cap = &mut net.cap;
    let ref g = & net.g;
    let s = net.source;
    let t = net.shink;
    let n = net.g.vertices_cnt();

    let mut alpha = usize::zero();
    for v in 0..n {
        for e in g.delta(&Vertex(v)) {
            alpha = max(alpha, cap[e.index]);
        }
    }
    let mut ans = 0;
    while alpha > usize::zero() {
        let mut i = 0;
        let mut isidxed = vec![0;n];
        let mut b = vec![usize::zero();n];
        let mut x = Vec::<Vertex>::new();
        x.push(s);
        isidxed[s.0] += 1;
        let mut ok = true;
        while x[i] != t {
            isidxed[x[i].0] += 1;
            for e in g.delta(&x[i]) {
                if cap[e.index] > usize::zero() && isidxed[e.to.0] != 2 {
                    b[e.to.0] = b[e.to.0] + cap[e.index];
                    if isidxed[e.to.0] == 0 && b[e.to.0] >= alpha {
                        x.push(e.to);
                        isidxed[e.to.0] += 1;
                    }
                }
            }
            if x.len() == i + 1 {
                alpha >>= 1;
                ok = false;
                break;
            }
            i = i + 1;
        }
        if !ok { continue; }

        let mut beta = vec![usize::zero();n];
        beta[t.0] = alpha;
        while i > 0 {
            isidxed[x[i].0] = 0;
            for rev in g.delta(&x[i]) {
                let e = g.eprop(rev);
                if isidxed[e.from.0] != 2 { continue; }
                let del = min(cap[e.index], beta[x[i].0]);
                cap[e.index] = cap[e.index] - del;
                cap[g.eprop(&e).index] = cap[g.eprop(&e).index] + del;
                if e.from == s {
                    ans += del;
                }
                if e.to == s {
                    ans -= del;
                }
                beta[x[i].0] = beta[x[i].0] - del;
                beta[e.from.0] = beta[e.from.0] + del;
            }
            i = i - 1;
        }
    }

    ans
}

 
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::<usize,usize>::new(n,0);
  
    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(&Vertex(x),&Vertex(y),w);
    }
  
    let mut net = Network::<usize>::build(&g,Vertex(0),Vertex(n - 1),|w| w.clone());
    println!("{}", fujishige(&mut net));
}



Measured memory_bytes: 5044