use std::collections::BinaryHeap;
use std::cmp::Reverse;
use std::fs::File;
use std::io::{BufReader, BufRead, Write};

struct Graph {
  n: usize,
  graph: Vec<Vec<(usize, i32)>>,
}

impl Graph {
  fn new(n: usize, edges: &Vec<(usize, usize, i32)>) -> Graph {
    let mut graph: Vec<Vec<(usize, i32)>> = vec![Vec::new(); n + 1];
    
    for edge in edges {
      graph[edge.0].push((edge.1, edge.2));
    }

    Graph {
      n,
      graph,
    } 
  }

  fn dijkstra(&mut self, root: usize) -> Vec<i32> {
    let mut dist = vec![1000000000; 1 + self.n];
    let mut heap = BinaryHeap::new();
    
    dist[root] = 0;
    heap.push(Reverse((dist[root], root)));
    
    while let Some(Reverse((dist_node, node))) = heap.pop() {
      if dist[node] == dist_node {
        for (neighbour, cost) in &self.graph[node] {
          if dist[node] + *cost < dist[*neighbour] {
            dist[*neighbour] = dist[node] + *cost;
            heap.push(Reverse((dist[*neighbour], *neighbour)));
          }
        }
      }
    }

    dist
  }
}

fn main() {
  let mut fin = BufReader::new(File::open("dijkstra.in").unwrap());

  let mut line = String::new();
  fin.read_line(&mut line).unwrap();
  let args: Vec<&str> = line.trim().split(' ').collect();

  assert_eq!(args.len(), 2);
  let n: usize = args[0].parse().unwrap();
  let m: usize = args[1].parse().unwrap();

  let mut edges: Vec<(usize, usize, i32)> = Vec::new();
  for _ in 0..m {
    let mut line = String::new();
    fin.read_line(&mut line).unwrap();
    let args: Vec<&str> = line.trim().split(' ').collect();
    
    let (a, b, cost): (usize, usize, i32) = (
      args[0].parse().unwrap(),
      args[1].parse().unwrap(),
      args[2].parse().unwrap(),
    );

    edges.push((a, b, cost));
  }

  let mut fout = File::create("dijkstra.out").unwrap();
  let dist = Graph::new(n, &edges).dijkstra(1);
  drop(edges);
  for i in 2..n+1 {
    fout.write(format!("{} ", if dist[i] < 1000000000 { dist[i] } else { 0 } ).as_bytes()).unwrap();
  }
}