#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define pb(a) push_back (a)
#define mp(a, b) make_pair (a, b)
#define INF 2000000000

int N, M;
vector <pair <int, int> > v[50005];
int lg[50005];
int visited[50005];
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > Hp;

void Citire () {
	ifstream fin ("dijkstra.in");
	fin >> N >> M;
	int a, b, c;
	for (int i = 0; i < M; i++)
	{
		fin >> a >> b >> c;
		v[a].pb (mp (b, c));
	}
	lg[1] = 0;
	Hp.push (mp (0, 1));
	for (int i = 2; i <= N; i++)
		lg[i] = INF, Hp.push (mp (INF, i));
}

void Business () {
	int a, b;
	while (!Hp.empty ())
	{
		if (visited[Hp.top ().second])
		{
			Hp.pop ();
			continue;
		}
		a = Hp.top ().second, b = v[a].size ();
		Hp.pop ();
		for (int i = 0; i < b; i++)
		{
			if (lg[v[a][i].first] > lg[a] + v[a][i].second)
			{
				lg[v[a][i].first] = lg[a] + v[a][i].second;
				Hp.push (mp (lg[v[a][i].first], v[a][i].first));
			}
		}
		visited[a] = 1;
	}
}

void Scriere () {
	ofstream fout ("dijkstra.out");
	for (int i = 2; i <= N; i++)
		if (lg[i] == INF) fout << "0 ";
		else fout << lg[i] << " ";
	fout.close ();
}

int main () {
	Citire ();
	Business ();
	Scriere ();
	return 0;
}