//
//  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"

template <typename T>
class InputReader {
private:
	FILE *input_file ;
	static const int SIZE = (1 << 17) ;
	int point ;
	char buffer[SIZE] ;
	__attribute__ ( (always_inline)) void advance() {
		++ point ;
		if (point == SIZE) {
			point = 0 ;
			fread (buffer, SIZE, 1, input_file) ;
		}
	}
public:
	InputReader() {}
	InputReader (const char *file_name) {
		input_file = fopen (file_name, "r") ;
		point = 0 ;
		fread (buffer, SIZE, 1, input_file) ;
	}
	__attribute__ ( (always_inline)) InputReader &operator >> (T &n) {
		for (; !isdigit (buffer[point]) ; advance()) ;
		n = 0 ;
		for (; isdigit (buffer[point]) ; advance()) {
			n = n * ( (1 << 3) + (1 << 1)) + buffer[point] - '0' ;
		}
		return *this ;
	}
} ;

InputReader<int> in ("dijkstra.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] << ' ' ;
	}
}