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

const int32_t MAX_N = 50000;
const int32_t MAX_DIST = 1000000000;

std::vector<std::pair<int32_t, int32_t>> adj[MAX_N];
int32_t dists[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("dijkstra.in");
	std::ofstream fout("dijkstra.out");

	int32_t n, m;
	fin >> n >> m;
	for(int32_t i = 0; i != m; ++i) {
		int32_t x, y, z;
		fin >> x >> y >> z;
		--x; --y;

		adj[x].push_back({ y, z });
	}

	for(int32_t i = 0; i != n; ++i)
		dists[i] = MAX_DIST;

	dists[0] = 0;
	q.push({ 0, 0 });

	while(!q.empty()) {
		std::pair<int32_t, int32_t> item = q.top();
		q.pop();

		if(dists[item.second] != item.first)
			continue;
		
		for(std::pair<int32_t, int32_t> edge : adj[item.second]) {
			int32_t newDist = item.first + edge.second;
			if(dists[edge.first] <= newDist)
				continue;
			
			dists[edge.first] = newDist;
			q.push({ newDist, edge.first });
		}
	}

	for(int32_t i = 1; i != n; ++i) {
		if(dists[i] == MAX_DIST)
			dists[i] = 0;
	}
	for(int32_t i = 1; i != n; ++i)
		fout << dists[i] << ' ';

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

	return 0;
}