#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1 << 30;

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	int n, m;
	scanf("%d%d", &n, &m);
	
	vector<vector<pair<int,int>>> neighbours(n);
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		neighbours[a - 1].push_back(make_pair(b - 1, c));
	}
	
	vector<int> dist(n, INF);
	dist[0] = 0;

	priority_queue<pair<int,int>> q;
	q.push(make_pair(0, 0));
	
	while (!q.empty()) {
		int node = q.top().second;
		if (dist[node] < q.top().first) {
			q.pop();
			continue;
		}
		q.pop();
		
		for (auto it : neighbours[node]) {
			if (dist[node] + it.second < dist[it.first]) {
				dist[it.first] = dist[node] + it.second;
				q.push(make_pair(dist[it.first], it.first));
			}
		}
	}
	for (int i = 1; i < n; ++i) {
		printf("%d ", dist[i]);
	}
	printf("\n");
	return 0;
}