//
//  main.cpp
//  dijkstra
//
//  Created by Eusebiu Rares on 23/09/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//

#include <iostream>
#include "fstream"
#include "vector"
#include "queue"

std::fstream in ("dijkstra.in", std::ios::in) ;
std::fstream out ("dijkstra.out", std::ios::out) ;

const int MV = 5e4 ;
using PII = std::pair<int, int> ;

int cost[MV + 1] ;

std::vector<PII> G[MV + 1] ;

void dijkstra(int start) {
	std::priority_queue<PII, std::vector<PII>, std::greater<PII> > pq ;
	pq.push({0, start}) ;
	while (!pq.empty()) {
		PII top = pq.top() ;
		pq.pop() ;
		if (cost[top.second] < top.first) {
			continue ;
		}
		cost[top.second] = top.first ;
		for (auto it : G[top.second]) {
			if (cost[top.second] + it.second < cost[it.first]) {
				cost[it.first] = cost[top.second] + it.second ;
				pq.push({cost[it.first], it.first}) ;
			}
		}
	}
}

int main(int argc, const char * argv[]) {
	int n, m, i, x, y, c ;
	in >> n >> m ;
	for (i = 1 ; i <= m ; ++ i) {
		in >> x >> y >> c ;
		G[x].push_back({y, c}) ;
	}
	for (i = 1 ; i <= n ; ++ i) {
		cost[i] = 1e9 ;
	}
	cost[1] = 0 ;
	dijkstra(1) ;
	for (i  = 2 ; i <= n ; ++ i) {
		if (cost[i] == 1e9) {
			cost[i] = 0 ;
		}
		out << cost[i] << ' ' ;
	}
}