//#include "../utils/PerformanceTimer.h"
#include <iostream>
#include <fstream>
#include <string>
//#include <list>
#include <vector>
#include <queue>
using namespace std;

//int e_009_dijkstra()
int main()
{
	const int MAX_N = 50000;
	//const int MAX_M = 250000;

	//PerformanceTimer timer;
	//timer.init();

	int n;//vertices
	int m;//edges
	//list< pair<int, int> >* adj_lists;
	vector< pair<int, int> > adj_lists[MAX_N + 1];
	ifstream ifs("dijkstra.in");	
	ifs>>n>>m;
	//adj_lists = new list<pair<int, int> >[n + 1];
	//read the edges and build the adjacency lists
	for (int i = 1; i <= m; i++)
	{
		int v1, v2, c12;
		ifs>>v1>>v2>>c12;
		adj_lists[v1].push_back(make_pair(v2, c12));		
	}
	ifs.close();

	//cost initialization
	const int MAX_COST = 999999999;
	//int* cost = new int[n + 1];
	int cost[MAX_N + 1];
	cost[1] = 0;
	for (int v = 2; v <= n; v++) cost[v] = MAX_COST;
	
	//char* in_queue = new char[n + 1];
	char in_queue[MAX_N + 1];
	for (int v = 1; v <= n; v++) in_queue[v] = 0;

	//the Dijkstra's algorithm
	//find the path of minimum cost between source node and all other nodes
	queue<int> queue_;
	queue_.push(1);
	in_queue[1] = 1;

	//int max_queue_size = 0;

	while (!queue_.empty())
	{
		//if (queue_.size() > max_queue_size) max_queue_size = queue_.size();
		//extract the next element to be processed
		int u = queue_.front();
		queue_.pop();
		in_queue[u] = 0;
		//updates the costs of the neighbors
		//for (list<pair<int, int> >::iterator it = adj_lists[u].begin(); it != adj_lists[u].end(); it++)
		for (vector< pair<int, int> >::iterator it = adj_lists[u].begin(); it != adj_lists[u].end(); it++)
		{
			int v = (*it).first;
			int c_uv = (*it).second;
			//if the current cost is higher than the cost of the current patch, update it
			if (cost[v] > cost[u] + c_uv)
			{
				cost[v] = cost[u] + c_uv;
				//if updated, add the vertex into the queue
				if (!in_queue[v])
				{
					queue_.push(v);
					in_queue[v] = 1;
				}
			}
		}
	}
	
	//if there is no connection between the node 1 and node v, cost[v] = 0;
	for (int v = 2; v <= n; v++) if (cost[v] == MAX_COST) cost[v] = 0;

	//cout<<timer.getElapsedTime()<<endl;
	//write the results to the output file
	ofstream ofs("dijkstra.out");
	for (int v = 2; v <= n; v++) ofs<<cost[v]<<" ";
	ofs.close();

	//release the memory
	//delete[] adj_lists;
	//delete[] cost;
	//delete[] in_queue;

	//cout<<timer.getElapsedTime()<<endl;
	//cout<<max_queue_size<<endl;

	return 0;
}