#if 1
#include <fstream>
#include <vector>
#include <limits.h>

using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int main()
{
	int i, nod, arc, x, y, cost;
	vector < int> vec[50005];
	vector < int> vec_cost[50005];
	int viz[50005] = { 0 }, dist[50005];
	cin >> nod >> arc;
	for (i = 1; i <= arc; i++) {
		cin >> x >> y >> cost;
		vec[x].push_back(y);
		vec_cost[x].push_back(cost);
	}

	dist[1] = 0;
	for (i = 2; i <= nod; i++)
		dist[i] = INT_MAX;
	for (i = 1; i <= nod; i++) {
		int val_min = INT_MAX;
		int index = -1;
		for (int j = 1; j <= nod; j++) {
			if (!viz[j] && dist[j] < val_min) {
				val_min = dist[j];
				index = j;
			}
		}
		viz[index] = 1;
		int lim = vec[index].size();
		for (int j = 0; j < lim; j++) {
			int vecin = vec[index][j];
			if (dist[vecin] > dist[index] + vec_cost[index][j])
				dist[vecin] = dist[index] + vec_cost[index][j];
		}
	}
	for (i = 2; i <= nod; i++)
		if (dist[i] == INT_MAX)
			cout << 0 << " ";
		else
			cout << dist[i] << " ";
	return 0;
}
#endif