use std::{error::Error, fs::File, io::{BufReader, LineWriter, Write, BufRead}, collections::BTreeSet};

const INF: i32 = 0x3f3f3f3f;

fn main() -> Result<(), Box<dyn Error>> {
    let f = File::open("dijkstra.in")?;
    let reader = BufReader::new(f);
    let f_out = File::create("dijkstra.out")?;
    let mut writer = LineWriter::new(f_out);
    let mut line_it = reader.lines();
    let first_line = line_it.next().unwrap()?;
    let mut first_line_it = first_line.split_whitespace();
    let n: usize = first_line_it.next().unwrap().parse()?;
    let m: i32 = first_line_it.next().unwrap().parse()?;
    let mut LA: Vec<Vec<(i32, i32)>> = Vec::with_capacity(n+1);
    let mut dist: Vec<i32> = Vec::with_capacity(n+1);
    LA.resize(n+1, Vec::new());
    dist.resize(n+1, INF);
    for _ in 0..m {
        let line = line_it.next().unwrap()?;
        let mut line_it = line.split_whitespace();
        let a: usize = line_it.next().unwrap().parse()?;
        let b: i32 = line_it.next().unwrap().parse()?;
        let c: i32 = line_it.next().unwrap().parse()?;
        LA[a].push((b,c));
    }
    let mut tree: BTreeSet<(i32, usize)> = BTreeSet::new();
    dist[1] = 0;
    tree.insert((0, 1usize));
    while !tree.is_empty() {
        let (_, node) = tree.pop_first().unwrap();
        for (next_node, next_cost) in &LA[node] {
            if dist[*next_node as usize] > dist[node] + next_cost {
                if dist[*next_node as usize] != INF {
                    tree.remove(&(dist[*next_node as usize], *next_node as usize));
                }
                dist[*next_node as usize] = dist[node] + next_cost;
                tree.insert((*next_node, *next_node as usize));
            }
        }
    }
    for i in 2..=n {
        write!(writer, "{} ", dist[i])?;
    }
    Ok(())
}