#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <limits>
using namespace std;

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

	int n;//vertices
	int m;//edges
	list<pair<int, int>>* adj_lists;
	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
	int* cost = new int[n + 1];
	cost[1] = 0;
	for (int v = 2; v <= n; v++) cost[v] = numeric_limits<int>::max();
	
	//the Dijkstra's algorithm
	//find the path of minimum cost between node source and all other nodes
	list<int> queue_;
	queue_.push_back(1);
	while (!queue_.empty())
	{
		//extract the next element to be processed
		int u = queue_.front();
		queue_.pop_front();
		//updates the costs of the neighbors
		for (list<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
				queue_.push_back(v);
			}
		}
	}
	
	//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;

	return 0;
}