#include <iostream>
#include <deque>
#include <fstream>
#include <limits>
using namespace std;

int main()
{
	string in_file = "dijsktra.in";
	string out_file = "dijsktra.out";

	int N, M;
	const int MAX_N = 10000;

	deque<pair<int, int>> adj[MAX_N + 1];
	
	//read the graph
	ifstream ifs(in_file);
	ifs >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		int A, B, C;
		ifs >> A >> B >> C;
		adj[A].push_back(make_pair(B, C));
	}

	ifs.close();
	
	unsigned int min_cost[MAX_N + 1]; //stores the minimum costs
	for (int i = 1; i <= N; i++) min_cost[i] = std::numeric_limits<unsigned int>::max();
	
	deque<int> Q;
	char is_in_queue[MAX_N + 1]; //if a node is already in queue
	for (int i = 1; i <= N; i++) is_in_queue[i] = 0;

	Q.push_back(1); is_in_queue[1] = 1; min_cost[1] = 0;
	while (!Q.empty())	{
		int v1 = Q.front();
		Q.pop_front();
		is_in_queue[v1] = 0;
		//parse the adiacency list of the extracted node
		for (deque<pair<int, int>>::iterator it = adj[v1].begin(); it != adj[v1].end(); it++)
		{
			int v2 = it->first;
			int cost_v1_v2 = it->second;
			unsigned int possible_cost = min_cost[v1] + cost_v1_v2;
			if (possible_cost < min_cost[v2]) {
				min_cost[v2] = possible_cost;
				//if already in queue, do not add the node in the queue, only update the minimum cost, the node has to be processed later
				if (!is_in_queue[v2]) {
					Q.push_back(v2); 
					is_in_queue[v2] = 1;
				}
			}
		}		
	} 

	ofstream ofs(out_file);
	for (int i = 2; i <= N; i++)
	{
		if (min_cost[i] != std::numeric_limits<unsigned int>::max()) ofs << min_cost[i] << " ";
		else ofs << 0 << " ";
	}
	ofs.close();

	return 0;
}