#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

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

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