#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

const int MAX_N = 50001;
const int MAX_M = 250001;

typedef std::pair<int, int> edge;


int n, m;
std::vector<edge> graph[MAX_N];
std::priority_queue<edge, std::vector<edge>, std::greater<edge>> heap;
int cost[MAX_N];

void read()
{
	std::ifstream input("dijkstra.in");
	input >> n >> m;
	int x, y, w;
	for (int edge(0); edge < m; ++edge) {
		input >> x >> y >> w;
		graph[x].push_back(std::make_pair(w, y));
	}
	input.close();
}

void print()
{
	std::ofstream output("dijkstra.out");
	for (int index(2); index <= n; ++index) {
		output << (cost[index] == std::numeric_limits<int>::max() ? 0 : cost[index]) << ' ';
	}
	output.put('\n');
	output.close();
}

void dijkstra()
{
	cost[1] = 0;
	for (int vertex(2); vertex <= n; ++vertex) {
		cost[vertex] = std::numeric_limits<int>::max();
	}
	heap.emplace(0, 1);
	int new_cost;
	while (!heap.empty()) {
		auto edge = heap.top();
		heap.pop();
		if (edge.first > cost[edge.second]) {
			continue;
		}
		for (auto it : graph[edge.second]) {
			new_cost = cost[edge.second] + it.first;
			if (new_cost < cost[it.second]) {
				cost[it.second] = new_cost;
				heap.emplace(new_cost, it.second);
			}
		}
	}
}

int main()
{
	read();
	dijkstra();
	print();
	return 0;
}