#include <fstream>
#include <vector>
#include <queue>
#define DIM 50001
#define INF 5000001
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, x, y, c, d[DIM];
bool viz[DIM];
vector<pair<int, int>> l[DIM];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int main() {
	fin >> n >> m;
	while (m--) {
		fin >> x >> y >> c;
		l[x].push_back({y, c});
	}
	for (int i = 1; i <= n; i++)
		d[i] = INF;
	d[1] = 0;
	pq.push({0, 1});
	while (!pq.empty()) {
		int nod = pq.top().second;
		pq.pop();
		if (viz[nod] == true)
			continue;
		viz[nod] = true;
		for (int i = 0; i < l[nod].size(); i++) {
			int vec = l[nod][i].first;
			int cost = l[nod][i].second;
			if (d[nod] + cost < d[vec]) {
				d[vec] = d[nod] + cost;
				pq.push({d[vec], vec});
			}
		}
	}
	for (int i = 2; i <= n; i++)
		if (d[i] == INF)
			fout << "0 ";
		else
			fout << d[i] << " ";
	return 0;
}