#![allow(unused)]
use std::cmp::Reverse;
fn main() {
let inp = readv::<usize>();
let (n, m) = (inp[0], inp[1]);
let mut adj = vec![vec![]; n];
let mut rev = vec![vec![]; n];
for _ in 0..m {
let inp = readv::<u64>();
let (u, v, w) = ((inp[0] - 1) as usize, (inp[1] - 1) as usize, inp[2]);
adj[u].push((v, w));
rev[v].push((u, w));
}
let inf = u64::MAX / 2;
let (dis1, _) = dijkstra(&adj, 0, inf);
let (dis2, _) = dijkstra(&rev, n - 1, inf);
let mut ans = inf;
for u in 0..n {
for &(v, w) in adj[u].iter() {
ans = ans.min(dis1[u] + dis2[v] + w / 2);
}
}
println!("{}", ans);
}
fn dijkstra<T>(adj: &Vec<Vec<(usize, T)>>, s: usize, inf: T) -> (Vec<T>, Vec<usize>)
where
T: std::ops::Add<Output = T> + Ord + Copy + Default,
{
let n = adj.len();
let mut que = std::collections::BinaryHeap::new(); // max heap
let mut dis = vec![inf; n];
let mut par = vec![!0; n];
dis[s] = T::default();
par[s] = s;
que.push((Reverse(dis[s]), s));
while let Some((Reverse(d), u)) = que.pop() {
if d > dis[u] {
continue;
}
for &(v, w) in adj[u].iter() {
let new_d = dis[u] + w;
if new_d < dis[v] {
dis[v] = new_d;
par[v] = u;
que.push((Reverse(dis[v]), v));
}
}
}
(dis, par)
}
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
fn readv<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_ascii_whitespace()
.map(|t| t.parse().ok().unwrap())
.collect()
}
fn reads() -> Vec<char> {
read::<String>().chars().collect::<Vec<char>>()
}
fn mapv<T, S, F: Fn(&T) -> S>(arr: &Vec<T>, f: F) -> Vec<S> {
arr.iter().map(f).collect()
}
fn join<T: ToString>(arr: &[T], sep: &str) -> String {
arr.iter()
.map(|x| x.to_string())
.collect::<Vec<String>>()
.join(sep)
}