#include <bits/stdc++.h>

using namespace std;

const int nMax = 50003;

const int INF = 1e9 + 3;

int n, m, dmin[nMax];
vector <pair<int, int>> g[nMax];
bool in_pq[nMax];

struct DminCmp {
	const bool operator() (const int &a, const int &b) {
		return dmin[a] > dmin[b];
	}
};

void Citire() {
	scanf("%d %d", &n, &m);

	for (int i = 1, from, to, cost; i <= m; ++i) {
		scanf("%d%d%d", &from, &to, &cost);
		g[from].emplace_back(to, cost);
	}
}

void initDistances() {
	dmin[1] = 0;

	for (int i = 2; i <= n; ++i)
		dmin[i] = INF;
}

void Dijkstra() {
	initDistances();
	priority_queue<int, vector<int>, DminCmp>pq;
	pq.push(1);
	int to, cost;

	while (!pq.empty()) {
		int node = pq.top();
		pq.pop();
		in_pq[node] = false;

		for (const auto& itr : g[node]) {
			tie(to, cost) = itr;

			if (dmin[node] < dmin[to] - cost) {
				dmin[to] = dmin[node] + cost;

				if (!in_pq[to]) {
					in_pq[to] = true;
					pq.push(to);
				}
			}
		}
	}
}

void PrintDistances() {
	for (int i = 2; i <= n; ++i) {
		if (dmin[i] == INF)
			printf("%d ", 0);
		else printf("%d ", dmin[i]);
	}
}
int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	Citire();
	Dijkstra();
	PrintDistances();
	return 0;
}