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

typedef std::pair<int32_t, int32_t> pair;
typedef std::vector<pair> vector;
typedef std::priority_queue<pair, vector, std::greater<pair>> queue;

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

vector adj[MAX_N];
queue q;
int32_t cost[MAX_N];
bool used[MAX_N];
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()) {
		int32_t ind = q.top().second;
		q.pop();
		if(used[ind])
			continue;
		used[ind] = true;
		
		for(pair next : adj[ind]) {
			if(used[next.first])
				continue;
			
			int32_t newCost = cost[ind] + 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)
		fout << cost[i] << ' ';

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

	return 0;
}