#include <bits/stdc++.h>

using namespace std;

const int Nmax = 50001;

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

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

void djk() {
	pq.push({ 1, 0 }); // incepem din 1
	while (!pq.empty()) {
		int nod = pq.top().nod, cost = pq.top().cost;
		pq.pop();

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

		for (auto& neighbor : mc[nod]) {
			if (cost + neighbor.second < d[neighbor.first]) {
				d[neighbor.first] = cost + neighbor.second;
				pq.push({ neighbor.first , d[neighbor.first] });
			}
		}
	}
}

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

	memset(d, 1000005, sizeof d);

	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] != 1000005)
			cout << d[i] << ' ';
		else
			cout << "0 ";
	}

	return 0;
}