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

use std::collections::BinaryHeap;

#[derive(PartialEq, Eq, Clone)]
struct Node {
    node: usize,
    dist: i32,
}

impl Ord for Node {
    fn cmp(&self, other: &Node) -> std::cmp::Ordering {
        other.dist.cmp(&self.dist)
    }
}


impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Node {
    fn new(node: usize, dist: i32) -> Self {
        Node {
            node, dist
        }
    }
}

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];

    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<Node> = BinaryHeap::new();
    let mut dp: Vec<i32> = vec![1e9 as i32; n + 1];

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

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

        //println!("node = {}, dist = {}", node, dist);

        if dist != dp[node] { continue; }

        for next in &g[node] {
            let (son, w) = *next;
            if dp[son] > dp[node] + w {
                dp[son] = dp[node] + w;
                //println!("{}, {}", son, dp[son]);
                pq.push(Node::new(son, dp[son]));
            }
        }
    }

    for i in 2..n+1 {
        write!(output, "{} ", if dp[i] == 1e9 as i32 { 0 } else { dp[i] }).unwrap();
    }
    writeln!(output).unwrap();
}