#include <bits/stdc++.h>

using namespace std;

#define NMAX 50005
#define INF 0x7F7F7F7F

vector<pair<int, int>> G[NMAX]; 

int dist[NMAX];
int n, m;

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

void dijkstra(int src)
{
	bool in_queue[NMAX] = {0};
	priority_queue<int, vector<int>, cmp> q;
	memset(dist, 0x7F, sizeof(dist));
	dist[src] = 0;
	q.push(src);
	while (!q.empty()) {
		int current = q.top();
		in_queue[current] = 0;
		q.pop();
		for (auto &[neighbour, cost] : G[current]) {
			if (dist[current] + cost < dist[neighbour]) {
				dist[neighbour] = dist[current] + cost;
				if (in_queue[neighbour] == 0) {
					q.push(neighbour);
					in_queue[neighbour] = 1;
				}
			}
		}
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdin);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, m;
		cin >> x >> y >> m;
		G[x].push_back({y, m});
	}
	dijkstra(1);
	for (int i = 2; i <= n; i++) {
		if (dist[i] == INF)
			dist[i] = 0;
		cout << dist[i] << ' ';
	}
	cout << '\n';
	return 0;
}