use std::io::{BufWriter, Write};
use std::fs::{File,self};
use std::collections::BinaryHeap;
macro_rules! parse_line {
    ($iter: expr, $($t: ty),+) => {{
      let line=$iter.next().unwrap();
      let mut parts = line.split_whitespace();
      ($(parts.next().unwrap().parse::<$t>().unwrap()), +)  
    }};
}
fn main() -> std::io::Result<()> {
    let content = fs::read_to_string("dijkstra.in")?;
    let mut lines = content.lines();
    let mut writer = BufWriter::new(File::create("dijkstra.out")?);
    let (n, m) =parse_line!(lines, usize, usize);
    let mut adj: Vec<Vec<(usize, i32)>> = vec![vec![]; n+1];
    let mut dist: Vec<i32> = vec![i32::MAX; n+1];
    let mut viz: Vec<i32> = vec![0; n+1];
    dist[1] = 0;
    for _ in 0..m {
        let (x, y, c) = parse_line!(lines, usize, usize, i32);
        adj[x].push((y, c));
    }
    let mut pq = BinaryHeap::new();
    pq.push((0,1));
    while let Some((_, node)) = pq.pop() {
        viz[node] = 0 ;
        for &(vec, cost) in &adj[node] {
            if dist[vec] > dist[node] + cost {
                dist[vec] = dist[node] + cost;
                if viz[vec] == 0 {
                    pq.push((dist[vec], vec));
                    viz[vec] = 1; 
                }
            }
        }
    }
    for &item in dist.iter().skip(2) {
        write!(writer,"{} ",item)?;
    }
    Ok(())
}