use std::fs::File;
use std::{io::*};

use std::collections::BinaryHeap;

fn main() {
    let in_file = File::open("dijkstra.in").unwrap();
    let out_file = File::create("dijkstra.out").unwrap();

    let mut input = BufReader::new(in_file);
    let mut output = BufWriter::new(out_file);

    let mut line = String::new();
    input.read_line(&mut line).unwrap();
    let stuff: Vec<usize> = line.split_whitespace().map(|x| x.parse().unwrap()).collect();
    let (n, _m) = (stuff[0], stuff[1]);
    let mut g: Vec<Vec<(usize, i32)>> = vec![Vec::default(); n + 1];
    let mut dp: Vec<i32> = vec![1e9 as i32; n + 1];

    for result_line in input.lines() {
        let line = result_line.unwrap();
        let edge: Vec<i32> = line.split_whitespace().map(|x| x.parse().unwrap()).collect();
        let (x, y, w) = (edge[0] as usize, edge[1] as usize, edge[2]);

        g[x].push((y, w));
    }

    let mut pq: BinaryHeap<(usize, i32)> = BinaryHeap::new();

    pq.push((1, 0));
    dp[1] = 0;

    while let Some(p) = pq.pop() {
        let (node, _) = p;

        for next in &g[node] {
            let (son, w) = *next;
            if dp[son] > dp[node] + w {
                dp[son] = dp[node] + w;
                pq.push((son, dp[son]));
            }
        }
    }

    for i in 2..n+1 {
        write!(output, "{} ", dp[i]).unwrap();
    }
    writeln!(output).unwrap();
}