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

use std::collections::BinaryHeap;

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

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

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<Node>> = 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(Node::new(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 = next.node;
            let w = next.dist;
            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();
}