#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <utility>
#define NMAX 50005
#define inf 1000000000
using namespace std;

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

int n, m;
vector < pair <int, int> > nodes[NMAX];
priority_queue < pair <int, int> > PQ;
int dist[NMAX];
bool viz[NMAX];

int main () 
{
	fin >> n >> m;
	int a, b, c;
	for (int i = 1; i <= m; ++i) {
		fin >> a >> b >> c;
		nodes[a].push_back(make_pair(b,c));
	}
	dist[1] = 0;
	for (int i = 2; i <= n; ++i) {
		dist[i] = inf;
	}
	PQ.push(make_pair(0, 1)); // prima oara distanta
	while (PQ.size()) {
		pair <int, int> aux = PQ.top();
		PQ.pop();
		int node = aux.second;
		if (viz[node]) {
			continue;
		}
		viz[node] = 1;
		for (int i = 0; i < nodes[node].size(); ++i) {
			if (dist[node] + nodes[node][i].second < dist[nodes[node][i].first]) {
				dist[nodes[node][i].first] = dist[node] + nodes[node][i].second;
				PQ.push(make_pair(-dist[nodes[node][i].first], nodes[node][i].first));
			}
		}
	}
	
	for (int i = 2; i <= n; ++i) {
		if (dist[i] == inf) {
			dist[i] = 0;
		}
		fout << dist[i] << " ";
	}
	fout << '\n';

	return 0;
}