#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

#ifdef LOCAL
#define fin cin
#define fout cout
#else
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#endif

#define int long long

vector<pair<int, long long>> adj[50001];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
vector<long long> costmin(50000, 1e18);

int main() {
	int n, m, a, b;
	long long c;
	fin >> n >> m;
	while (m--) {
		fin >> a >> b >> c;
		adj[a].push_back({b, c});
	}
	pq.push({0, 1});
	costmin[1] = 0;
	while (!pq.empty()) {
		auto [cost, nod] = pq.top();
		pq.pop();
		if (costmin[nod] != cost)
			continue;
		for (auto [vecin, cost_vecin]:adj[nod])
			if (costmin[nod] + cost_vecin < costmin[vecin]) {
				costmin[vecin] = costmin[nod] + cost_vecin;
				pq.push({costmin[vecin], vecin});
			}
	}
	for (int i=2; i<=n; i++)
		fout << (costmin[i] < 1e9 ? costmin[i] : 0) << ' ';
}