use std::collections::VecDeque;

#[derive(Debug, Clone)]
struct Edge {
    capacity: i64,
    to: usize,
    // If edge is u-> edge{to:v, rev:i},
    // then, the reverse edge would be edges[v][rev]
    rev: usize,
}

impl Edge {
    fn new(to: usize, capacity: i64, rev: usize) -> Self {
        Self { to, capacity, rev }
    }
}

const BIG: i64 = 100_000_000_000;
#[derive(Debug, Clone)]
struct Dinic {
    level: Vec<usize>,
    checked: Vec<usize>, // The memolized DFS.
    edges: Vec<Vec<Edge>>,
    size: usize,
}

impl Dinic {
    fn new(graph: Vec<Vec<(usize, i64)>>) -> Self {
        let size = graph.len();
        let level = vec![size + 1; size];
        let checked = vec![size + 1; size];
        let mut edges = vec![vec![]; size];
        for (from, targets) in graph.iter().enumerate() {
            for &(to, cap) in targets {
                let rev_from = edges[to].len();
                let rev_to = edges[from].len();
                edges[from].push(Edge::new(to, cap, rev_from));
                edges[to].push(Edge::new(from, 0, rev_to));
            }
        }
        Self {
            level,
            checked,
            edges,
            size,
        }
    }
    // Update level member. Calculate the smallest 'number' of edges from `start`.
    fn bfs(&mut self, start: usize) {
        self.level = vec![self.size+1;self.size];
        let mut queue = VecDeque::new();
        self.level[start] = 0;
        queue.push_back(start);
        while let Some(from) = queue.pop_front() {
            for edge in &self.edges[from] {
                if edge.capacity > 0 && self.level[edge.to] == self.size + 1 {
                    self.level[edge.to] = self.level[from] + 1;
                    queue.push_back(edge.to);
                }
            }
        }
    }
    // Search for an argument path.
    // return the flow value
    fn dfs(&mut self, node: usize, end: usize, flow: i64) -> i64 {
        // eprintln!("->{}",node);
        if node == end {
            return flow;
        }
        for edge_idx in self.checked[node]..self.edges[node].len() {
            self.checked[node] = edge_idx;
            let edge = self.edges[node][edge_idx].clone();
            //eprintln!("{},{} ({})",node,edge.to,edge.capacity);
            if edge.capacity > 0 && self.level[node] < self.level[edge.to] {
                let next_flow = self.dfs(edge.to, end, std::cmp::min(edge.capacity, flow));
                if next_flow > 0 {
                    self.edges[node][edge_idx].capacity -= next_flow;
                    self.edges[edge.to][edge.rev].capacity += next_flow;
                    return next_flow;
                }
            }
        }
        return 0;
    }
    fn max_flow(&mut self, start: usize, end: usize) -> i64 {
        let mut flow = 0;
        loop {
            self.bfs(start);
            if self.level[end] == self.size + 1 {
                return flow;
            }
            self.checked = vec![0; self.size];
            loop {
                let f = self.dfs(start, end, BIG);
                // eprintln!("flow: {}",f);
                if f > 0 {
                    flow += f;
                } else {
                    break;
                }
            }
        }
    }
}

fn solve(graph: Vec<Vec<(usize, i64)>>, start: usize, end: usize){
    let mut dinic = Dinic::new(graph);
    let flow = dinic.max_flow(start, end);
    println!("{}",flow);
}

use std::io::{BufRead, BufReader};
fn main() {
    let mut read = BufReader::new(std::io::stdin())
        .lines()
        .filter_map(|e| e.ok());
    let (v, _e) = {
        let line = read.next().unwrap();
        let line: Vec<&str> = line.split(' ').collect();
        let v: usize = line[0].parse().unwrap();
        let e: usize = line[1].parse().unwrap();
        (v, e)
    };
    let graph = {
        let mut graph: Vec<Vec<_>> = vec![vec![]; v]; // Adj list
        for edge in read {
            let mut edge = edge.split(' ');
            let start: usize = edge.next().unwrap().parse().unwrap();
            let end: usize = edge.next().unwrap().parse().unwrap();
            let weight: i64 = edge.next().unwrap().parse().unwrap();
            graph[start].push((end, weight));
        }
        graph
    };
    solve(graph, 0, v-1);
}



Measured memory_bytes: 5060