#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn get_idx(i: usize, x: usize, y: usize, w: usize) -> usize { i + x * 2 + y * 2 * w } fn main() { let v = read_vec::(); let (n, m) = (v[0], v[1]); let mut cost_dict = HashMap::new(); for i in 0..m { let v = read_vec::(); let (h, w, c) = (v[0] as usize - 1, v[1] as usize - 1, v[2]); cost_dict.insert((h, w), c); } let mut edges = vec![vec![]; n * n * 2]; for y in 0..n { for x in 0..n { let cost; let cur0 = get_idx(0, x, y, n); let cur1 = get_idx(1, x, y, n); if cost_dict.contains_key(&(y, x)) { cost = cost_dict[&(y, x)]; } else { cost = 0; } for (adj_x, adj_y) in get_adjacents(x, y, n, n) { let adj0 = get_idx(0, adj_x, adj_y, n); let adj1 = get_idx(1, adj_x, adj_y, n); edges[adj0].push((cur0, cost + 1)); edges[adj1].push((cur1, cost + 1)); edges[adj0].push((cur1, 1)); } } } let d = solve(&edges, 0); let ans = d[get_idx(1, n - 1, n - 1, n)]; println!("{}", ans); } fn get_adjacents(x: usize, y: usize, w: usize, h: usize) -> Vec<(usize, usize)> { let mut adjacents = vec![]; if x > 0 { adjacents.push((x - 1, y)); } if y > 0 { adjacents.push((x, y - 1)); } if y < h - 1 { adjacents.push((x, y + 1)); } if x < w - 1 { adjacents.push((x + 1, y)); } adjacents } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } const INF: i64 = 100000_00000_00000; fn solve(edges: &Vec>, start_idx: usize) -> Vec { let num_apexes = edges.len(); let mut d = vec![INF; num_apexes]; d[start_idx] = 0; let mut que = std::collections::BinaryHeap::new(); que.push((std::cmp::Reverse(0), start_idx)); while let Some((u, v)) = que.pop() { if d[v] < u.0 { continue; } for e in &edges[v] { if d[v] != INF && d[e.0] > d[v] + e.1 { d[e.0] = d[v] + e.1; que.push((std::cmp::Reverse(d[e.0]), e.0)); } } } d }