#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

#define INF 1000000

using namespace std;

int main() {
	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	int n, m, i, x, y, d, q;
	vector <pair <int, int>> *edge;
	queue<int> que;
	

	scanf("%d %d", &n, &m);
	edge = new vector <pair <int, int>>[m];

	vector <bool> viz(n + 1, false);
	vector <int> dis(n + 1, INF);

	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &x, &y, &d);
		edge[x].push_back(make_pair(y, d));
	}
	dis[1] = 0;
	viz[1] = true;
	que.push(1);
	while (!que.empty()) {
		q = que.front();
		que.pop();
		
		for (i = 0; i < edge[q].size(); i++) {
			

			if (dis[q] + edge[q][i].second < dis[edge[q][i].first]) {
				dis[edge[q][i].first] = dis[q] + edge[q][i].second;
				if (viz[edge[q][i].first] == false) {

					viz[edge[q][i].first] = true;
					que.push(edge[q][i].first);

				}
			}

		}

	}

	for (i = 2; i <= n; i++) {
		if (dis[i] != INF) printf("%d ", dis[i]);
		else printf("0 ");
	}

	return 0;
}