#include <bits/stdc++.h>

using namespace std;

const int Nmax = 5e4 + 1;

struct str {
	int nod, cost;
	bool operator < (const str& aux) const {
		return cost > aux.cost;
	}
};

int x, y, c, n, m;
int d[Nmax];
vector<pair<int, int>> mc[Nmax];
priority_queue<str> pq;
// priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// priority_queue<Type, Container, Comparison>

void djk() {
	pq.push({ 1, 0 });
	d[1] = 0;

	while (!pq.empty()) {
		int nod = pq.top().nod, cost = pq.top().cost;
		pq.pop();

		if (d[nod] < cost) {
			continue;
		}

		for (auto& i : mc[nod]) {
			if (d[i.first] > i.second + d[nod] || d[i.first] == 0) {
				d[i.first] = i.second + d[nod];
				pq.push({ i.first, d[i.first] });
			}
		}

	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	while (m--) {
		cin >> x >> y >> c;
		mc[x].push_back({ y, c });
	}

	djk();

	for (int i = 2; i <= n; ++i) {
		if (d[i] == 100005)
			cout << 0 << ' ';
		else
			cout << d[i] << ' ';
	}

	return 0;
}