#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>

//#define INT_MAX 0x7FFFFFFF

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


int distances[50001];

struct node
{
	int id;
	int distance;
	bool operator<(const node& rhs) const
	{
		return distance > rhs.distance;
	}
};

struct adjNode
{
	int nodeId;
	int weight;
	
};
vector<adjNode> graph[250001];
void input(int edges)
{
	for (int i = 1; i <= edges; i++)
	{
		int a = 0, b = 0, weight = 0;
		f >> a >> b >> weight;
		adjNode node;
		node.nodeId = b;
		node.weight = weight;

		graph[a].push_back(node);
	}
}

void dijkstra(int nodes, int edges,int startNode)
{
	///determines the minimum distance from the source node to each node
	vector<node> heap;
	make_heap(heap.begin(), heap.end());

	for (int i = 1; i <= nodes; i++)
		distances[i] = INT_MAX;
	
	node start;
	start.id = startNode;
	start.distance = 0;

	heap.push_back(start);
	push_heap(heap.begin(), heap.end());

	while(!heap.empty())
	{
		node crtnode = heap.front();

		
		
		//heap.pop_back();
		//make_heap(heap.begin(), heap.end());

		for (auto adjNode : graph[crtnode.id])
		{
			if (distances[adjNode.nodeId] > crtnode.distance + adjNode.weight)
			{
				distances[adjNode.nodeId] = crtnode.distance + adjNode.weight;
				node thisNode;
				thisNode.id = adjNode.nodeId;
				thisNode.distance = distances[adjNode.nodeId];

				heap.push_back(thisNode);
				push_heap(heap.begin(), heap.end());
			}
		}
		pop_heap(heap.begin(), heap.end());
		heap.pop_back();
	}

}




int main()
{
	clock_t start = clock();

	
	
	int nodes = 0, edges = 0;
	f >> nodes >> edges;

	input(edges);

	dijkstra(nodes,edges,1);

	for (int i = 2; i <= nodes; i++)
		if (distances[i] == INT_MAX)
			g << "0 ";
		else
			g << distances[i] << " ";

	
	
	f.close();
	g.close();


	clock_t end = clock();
	float seconds = (float)(end - start) / CLOCKS_PER_SEC;
	printf("%f", seconds);
	char c;
	cin >> c;
	
	return 0;
}