#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
const int MX = 1e5+1, INF = 1e9;
int n, m, x, y, c;
vector<ii> adj[MX];
int dist[MX];

int main() {
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &x, &y, &c);
		adj[x].push_back(ii(y, c));
	}
	for (int i = 0; i < MX; i++) {
		dist[i] = INF;
	}
	dist[1] = 0;
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push(ii(0, 1));
	while (!pq.empty()) {
		ii t = pq.top();
		pq.pop();
		int d = t.first, u = t.second;
		if (d == dist[u]) {
			for (int i = 0; i < adj[u].size(); i++) {
				int v = adj[u][i].first, ed = adj[u][i].second;
				if (d + ed < dist[v]) {
					dist[v] = d+ed;
					pq.push(ii(dist[v], v));
				}
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		printf("%d ", (dist[i] == INF ? 0 : dist[i]));
	}
	return 0;
}