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

using namespace std;

#define INT_MAX 1000000

vector <int> graph[50005];
vector <int> graphC[50005];
priority_queue< pair<int, int> > myheap;
int dist[50005];
int viz[50005];

int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	int n, m;
	f >> n >> m;
	int a, b, c;
	for (int i = 0; i < m; i++)
	{
		f >> a >> b >> c;
		graph[a].push_back(b);
		graphC[a].push_back(c);
	}
	dist[1] = 0;
	myheap.push(make_pair(-dist[1], 1));
	for (int i = 2; i <= n; i++) {
		dist[i] = INT_MAX;
		myheap.push(make_pair(-dist[i], i));
	}
	int index;
	while (!myheap.empty())
	{
		pair<int, int>p = myheap.top();
		index = p.second;
		myheap.pop();
		if (viz[index] == 1)
			continue;
		else
		{
			viz[index] = 1;
			int lim = graph[index].size();
			for (int i = 0; i < lim; i++)
			{
				int vecin = graph[index][i];
				if (dist[vecin] > (dist[index] + graphC[index][i]))
				{
					dist[vecin] = dist[index] + graphC[index][i];
					myheap.push(make_pair(-dist[vecin], vecin));
				}
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (dist[i] == INT_MAX)
			dist[i] = 0;
		g << dist[i] << " ";
	}
	return 0;
}