use core::net;
use std::{cmp::{max, min}, collections::{HashMap, VecDeque}, fs::{self, File, OpenOptions}, io::{BufRead, BufReader, BufWriter, Read, Write}};
type Graph = Vec<Vec<(usize, usize)>>;
type Flow = Vec<Vec<(usize, usize, usize)>>; //3 numbers, one keeps the initial capacity information
type ResidualGraph = Vec<Vec<(usize, usize, bool)>>; //keep a boolean to know if the direction is reversed

const INF: usize = 1_000_000_000;

fn main() {
    // read
    let mut file = File::open("maxflow.in").unwrap();
    let mut rdr = BufReader::new(file);
    let mut line = String::new();
    rdr.read_line(&mut line);
    let mut it = line.split_whitespace().map(|x| x.parse::<usize>().unwrap());
    let n = it.next().unwrap();
    let m = it.next().unwrap();
    let mut adj: Graph = vec![vec![]; n + 1];
    for _ in 0..m {
        let mut line = String::new();
        rdr.read_line(&mut line);
        let mut it = line.split_whitespace().map(|x| x.parse::<usize>().unwrap());
        let u = it.next().unwrap();
        let v = it.next().unwrap();
        let c = it.next().unwrap();
        adj[u].push((v, c));
    }
    // dbg!(&adj);

    let mut flow: Flow = vec![vec![]; n + 1];
    // let mut map: Vec<Vec<(usize, usize)>> = vec![vec![(0, 0); n + 1]; n + 1];
    for u in 1..=n {
        for &(v, c) in adj[u].iter() {
            let edge = (v, 0, c);
            flow[u].push(edge);
            // map[u][v] = (0, c);
        }
    }

    loop {
        // dbg!(&flow);
        // construct res graph
        let mut residual: ResidualGraph = vec![vec![]; n + 1];
        for u in 1..=n {
            for &(v, f, c) in flow[u].iter() {
                if c > f {
                    residual[u].push((v, c - f, true));
                }
                if f > 0 {
                    residual[v].push((u, f, false));
                }
            }
        }
        // dbg!(&residual);

        // find augmenting path in the residual
        let mut d = VecDeque::new();
        let mut dist = vec![INF; n + 1];
        let mut paths = vec![(0, 0, false); n + 1]; // parent vector of the augmenting path
        d.push_back(1);
        dist[1] = 0;
        while !d.is_empty() {
            let u = d.pop_front().unwrap();
            for &edge in residual[u].iter() {
                let (v, w, dir) = edge;
                if dist[u] + 1 < dist[v] {
                    dist[v] = dist[u] + 1;
                    d.push_back(v);
                    paths[v] = (u, w, dir);
                }
            }
        }
        // dbg!(&paths);

        // update flow
        if dist[n] == INF {
            break;
        } else {
            let mut v = n;
            let mut edge = &paths[n];
            let mut flux_update = INF;
            while edge.0 != 0 {
                flux_update = min(edge.1, flux_update);
                edge = &paths[edge.0];
            }
            let mut edge = &paths[n];
            // dbg!(edge);
            let mut u; let mut w; let mut dir;
            (u, w, dir) = (edge.0, edge.1, edge.2);

            while u != 0 {
                if dir {
                    // the updates are inefficient, I probably need a different structure to access the flows in O(1)
                    flow[u].iter_mut()
                        .filter(|(end, _, _)| *end == v)
                        .for_each(|(end, f, c)| *f += flux_update);

                    // dbg!(&flow);
                } else {
                    flow[v].iter_mut()
                        .filter(|(end, _, _)| *end == u)
                        .for_each(|(end, f, c)| *f -= flux_update);

                    // dbg!(&flow);
                }
                edge = &paths[u];
                v = u;
                (u, w, dir) = (edge.0, edge.1, edge.2);
            }
        }
    }

    let max_flow: usize = flow[1].iter().map(|&(_, f, _)| f).sum();

    // write
    let ofile= OpenOptions::new().create(true).write(true).truncate(true).open("maxflow.out").unwrap();
    let mut out = BufWriter::new(ofile);
    writeln!(out, "{}", max_flow);
}