#include <iostream>
#include <fstream>
#include <stdint.h>
#include <utility>
#include <vector>
#include <queue>

const int32_t MAX_N = 50000;
const int32_t MAX_COST = 1000000000;

int32_t cost[MAX_N];
std::vector<std::pair<int32_t, int32_t>> adj[MAX_N];
std::priority_queue<std::pair<int32_t, int32_t>, std::vector<std::pair<int32_t, int32_t>>, std::greater<std::pair<int32_t, int32_t>>> q;
int main() {
	std::ifstream fin("djikistra.in");
	std::ofstream fout("djikistra.out");
	
	int32_t n, m;
	fin >> n >> m;

	for(int32_t i = 0; i != m; ++i) {
		int32_t a, b, c;
		fin >> a >> b >> c;
		--a; --b;

		adj[a].push_back({ b, c });
	}

	for(int32_t i = 1; i != n; ++i)
		cost[i] = MAX_COST;

	q.push({ 0, 0 });

	while(!q.empty()) {
		auto val = q.top();
		q.pop();

		int32_t nodeCost = val.first;
		int32_t ind = val.second;

		if(cost[ind] < nodeCost)
			continue;
		
		for(auto next : adj[ind]) {
			int32_t newCost = nodeCost + next.second;
			if(newCost >= cost[next.first])
				continue;
			
			cost[next.first] = newCost;
			q.push({ newCost, next.first });
		}
	}

	for(int32_t i = 1; i != n; ++i) {
		if(cost[i] == MAX_COST) {
			fout << "0 ";
		} else {
			fout << cost[i] << ' ';
		}
	}

	fin.close();
	fout.close();

	return 0;
}