#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");

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

struct adjNode
{
	int nodeId;
	int weight;
	
};

void input(vector<adjNode>* graph, 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(vector<adjNode>* graph, int nodes, int edges,int startNode, int* distance)
{
	///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++)
		distance[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 (distance[adjNode.nodeId] > crtnode.distance + adjNode.weight)
			{
				distance[adjNode.nodeId] = crtnode.distance + adjNode.weight;
				node thisNode;
				thisNode.id = adjNode.nodeId;
				thisNode.distance = distance[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();

	vector<adjNode>* graph= new vector<adjNode>[250001];
	int* distances = (int*)malloc(50001 * sizeof(int));

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

	input(graph, edges);

	dijkstra(graph, nodes,edges,1, distances);

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

	delete[] graph;
	free(distances);
	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;
}