// InfoArenaDijkstra.cpp : This file contains the 'main' function. Program execution begins and ends there.
//


//#include "pch.h"
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

int MAX = 1 << 30;
#define dim 50001

struct Node {
	int number,value = MAX;
};

void AddNewNode(vector<Node> graph[dim],int x,int y, int cost) {
	Node newNode;
	newNode.number = y;
	newNode.value = cost;
	graph[x].push_back(newNode);
}

bool searched[dim];
int distanceValues[dim];
Node heapArray[dim];
int heapArrayIndex = 0;


struct Comparison {
	bool operator()(const pair<int, int> left, const pair<int, int> right) const {
		return left.first > right.first;
		}
};

void ApplyHeapStructure(Node node) {
	int minVal = MAX, minIndex = -1;
	
	for (int i = heapArrayIndex - 1; i >= 0; i = (i-1)/2) {
		if (heapArray[(i - 1) / 2].value > heapArray[i].value) {
			swap(heapArray[(i - 1) / 2], heapArray[i]);
		}
		else break;
	}
}

void InsertElementIntoHeap(Node node) {

	if (heapArrayIndex == 0) {
		heapArray[heapArrayIndex++] = node;
		return;
	}

	heapArray[heapArrayIndex++] = node;

	ApplyHeapStructure(node);
}

void ReconstructHeap(int index = 0);

Node GetLowestValueNode() {
	Node returnNode = heapArray[0];

	heapArray[0] = heapArray[heapArrayIndex-1];
	--heapArrayIndex;

	ReconstructHeap();

	return returnNode;
}

void ReconstructHeap(int index) {

	if (index >= heapArrayIndex)return;
	int leftIndex = 2 * index + 1;
	int rightIndex = 2 * index + 2;
	int currentIndex = index;

	if (heapArray[leftIndex].value < heapArray[currentIndex].value) {
		currentIndex = leftIndex;
	}

	if (heapArray[rightIndex].value < heapArray[currentIndex].value) {
		currentIndex = rightIndex;
	}

	if (currentIndex != index) {
		swap(heapArray[currentIndex], heapArray[index]);
		ReconstructHeap(currentIndex);
	}
}

void Dijktra(int startNode, vector<Node> graph[dim],int n) {
	distanceValues[startNode] = 0;

	Node node;
	node.number = startNode;
	node.value = 0;

	InsertElementIntoHeap(node);
	
	while (heapArrayIndex>0) {
		int node = GetLowestValueNode().number;
		searched[node] = true;

		for(Node x : graph[node])
		{
			if (searched[x.number] == true)continue;

			if ((distanceValues[node] + x.value) < distanceValues[x.number]) {
				distanceValues[x.number] = distanceValues[node] + x.value;
			}

			Node newNode;
			newNode.number = x.number;
			newNode.value = distanceValues[x.number];

			InsertElementIntoHeap(newNode);
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (distanceValues[i] == MAX)distanceValues[i] = 0;
	}
}


int main()
{
	int n, m, x, y, cost;

	int startNode = 1;

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

	f >> n >> m;

	for (int i = 1; i <= n; ++i) {
		searched[i] = false;
		distanceValues[i] = MAX;
	}
	vector<Node> graph[dim];

	while (m--) {
		f >> x >> y >> cost;

		AddNewNode(graph, x, y, cost);
	}

	Dijktra(startNode,graph,n);

	for (int i = 2; i <= n; ++i) {
		g << distanceValues[i] << " ";
	}
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file