#include <fstream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n;
const int nMax = 50000 + 1;
const int oo = 1e9;
vector<int>d(nMax, 0);
vector<pair<int, int>>G[nMax];
bool inQueue[nMax];
void dijkstra(int nodStart) {
	for (int i = 1; i <= n; ++i)
		d[i] = oo;
	d[nodStart] = 0;
	priority_queue<int, vector<int>, greater<int>>pQ;
	pQ.push(nodStart);
	memset(inQueue, false, sizeof inQueue);
	inQueue[nodStart] = true;
	while (!pQ.empty()) {
		int nodCurent = pQ.top();
		pQ.pop();
		inQueue[nodCurent] = false;
		for (auto i : G[nodCurent]) {
			int nextNod = i.first;
			int cost = i.second;
			if (d[nextNod] > d[nodCurent] + cost) {
				d[nextNod] = d[nodCurent] + cost;
				if (!inQueue[nextNod]) {
					inQueue[nextNod] = true;
					pQ.push(nextNod);
				}
			}
		}
	}
}
int main() {
	int m;
	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y, z;
		f >> x >> y >> z;
		G[x].push_back({ y,z });
	}
	dijkstra(1);
	for (int i = 2; i <= n; ++i)
		if (d[i] == oo)
			g << 0 << ' ';
		else
			g << d[i] << ' ';
	return 0;
}