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

#define INF 0x7ffff


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


void solve(int sursa, int N, std::vector<int> *graf, std::vector<int> *cost, std::vector<int> dist) {		

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

	
	while (!qu.empty()) {
		std::pair<int,int> n = qu.top();
		dist[n.first] = n.second;
		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));
			}
		}
	
	}	

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

	fout << '\n';
	
}



int main() {


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

	std::vector<int> graf[N+1];
	std::vector<int> cost[N+1];
	std::vector<int> dist(N+1);
 
	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);		
	
	} 
   
	int sursa = 1;
	solve(sursa ,N, graf, cost, dist);

    return 0;
}