#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

#define INF 0x7ffff


std::ifstream fin ("dijkstra.in");
std::ofstream fout ("dijkstra.out");

std::vector<int> graf[50001];
std::vector<int> cost[50001];
std::vector<int> dist(50001);


void solve(int N) {		


	dist[1] = 0;
	for (int i = 2; i <= N; i++) 
		dist[i] = INF;
	
	
	std::priority_queue<std::pair<int,int> > qu;
	//fist ->index nod;
	//second ->dist sursa - nod
	qu.push(std::make_pair(1, 0));	

	
	while (!qu.empty()) {
		std::pair<int,int> n = qu.top();
		qu.pop();
	
		for (size_t i = 0; i < graf[n.first].size(); i++) {
			int lung = cost[n.first][i];
			if (dist[graf[n.first][i]] > n.second + lung ) {
				qu.push(std::make_pair(graf[n.first][i], n.second + lung));
				dist[graf[n.first][i]] = n.second + lung;			
			}
		}
	
	}	

	for (int i = 2; i <= N; i++)
		if (dist[i] != INF) fout << dist[i] << " ";
		else fout << 0 << " ";


	fout << '\n';
	
}



int main() {

	int T;
	int N, M;
	fin >> N >> M;

 
	for (int i = 1; i <= M; i++) {
		int x, y, z;
	
		fin >> x >> y >> z;
		graf[x].push_back(y);
		cost[x].push_back(z);		

	} 
   
solve(N);
    return 0;
}