#include <bits/stdc++.h>
using namespace std;

#define NMAX 50005
#define INF 0x7F7F7F7F

int dist[NMAX];

struct cmp {
	bool operator()(int x, int y) {
		return dist[x] > dist[y];
	}
};

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

	int n, m;
	scanf("%d%d", &n, &m);

	vector<pair<int, int>> G[NMAX];
	for (int i = 1, x, y, c; i <= m; ++i) {
		scanf("%d%d%d", &x, &y, &c);
		G[x].push_back({y, c});
	}

	memset(dist, 0x7F, sizeof(dist));
	dist[1] = 0;

	priority_queue<int, vector<int>, cmp> q;
	q.push(1);

	bool in_queue[NMAX] {};

	while (!q.empty()) {
		int curr = q.top();
		q.pop();
		in_queue[curr] = 0;

		for (const auto &[neigh, cost] : G[curr]) {
			if (dist[curr] + cost < dist[neigh]) {
				dist[neigh] = dist[curr] + cost;
				if (!in_queue[neigh]) {
					q.push(neigh);
					in_queue[neigh] = 1;
				}
			}
		}
	}

	for (int i = 2; i <= n; ++i)
		printf("%d ", dist[i] == INF ? 0 : dist[i]);
	puts("");
}