#include <stdlib.h>
#include <fstream>
#include <string.h>
#include <vector>
#include <time.h>
#include <iostream>
using namespace std;

#ifndef _FIBONACCI_HEAP_H_
#define _FIBONACCI_HEAP_H_

#include <stdio.h>
#include <vector> 


enum State
{
	LABELED, UNLABELED, SCANNED
};

class Node;

class Edge
{
private:
public:
	Node* tail;
	Node* head;
	int length;
	int delta;

	Edge(Node* tail, Node* head, int length);
};


class Node
{
private:
public:
	Node * parent;
	Node * leftSibling, * rightSibling;
	Node * children; 
	Node * pred;

	Node(int data, int key);
	Node();

	int data;
	int key;
	int rank;

	std::vector<Edge*> incomingEdges;
	std::vector<Edge*> outgoingEdges;

	State state;

	bool addChild(Node * node);
	bool addSibling(Node * node);
	bool remove();
	
	Node* leftMostSibling();
	Node* rightMostSibling();

	void addIncomingEdge(Edge * edge);
	void addOutgoingEdge(Edge * edge);

};

class FiboHeap
{
private:
	Node* rootListByRank[100];

	bool link(Node* root);	
	Node * minRoot;

public:

	FiboHeap();
	FiboHeap(Node *root);

	~FiboHeap();

	bool isEmpty();
	bool insertVertex(Node * node);	
	void decreaseKey(int delta, Node* vertex);

	Node* findMin();
	Node* deleteMin();
};

#endif

Edge::Edge(Node* tail, Node* head, int length)
{
	this->tail = tail;
	this->head = head;
	this->length = length;
}

Node::Node(int data, int key)
{
	this->key = key;
	this->data = data;
	parent = NULL;
	children = NULL;
	leftSibling = NULL;
	rightSibling = NULL;
	pred = NULL;
	rank = 0;
	state = UNLABELED;
}

Node::Node()
{
	parent = NULL;
	children = NULL;
	leftSibling = NULL;
	rightSibling = NULL;
	pred = NULL;
	rank = 0;
	state = UNLABELED;
}

bool Node::addChild(Node *node)
{
	if(children != NULL)
		children->addSibling(node);
	else
	{
		children = node;
		node->parent = this;
		rank = 1;
	}

	return true;
}

bool Node::addSibling(Node *node)
{
	Node* temp = rightMostSibling();
	if(temp == NULL)
		return false;

	temp->rightSibling = node;
	node->leftSibling = temp;
	node->parent = this->parent;
	node->rightSibling = NULL;

	if(parent)
		parent->rank++;

	return true;
}

bool Node::remove()
{
	if(parent)
	{
		parent->rank--;
		if(leftSibling)
			parent->children = leftSibling;
		else if(rightSibling)
			parent->children = rightSibling;
		else
			parent->children = NULL;
	}	
	
	if(leftSibling)
		leftSibling->rightSibling = rightSibling;
	if(rightSibling)
		rightSibling->leftSibling = leftSibling;
	
	leftSibling = NULL;
	rightSibling = NULL;
	parent = NULL;

	return true;
}

void Node::addIncomingEdge(Edge * edge)
{
	incomingEdges.push_back(edge);
}

void Node::addOutgoingEdge(Edge * edge)
{
	outgoingEdges.push_back(edge);
}


Node* Node::leftMostSibling()
{
	if(this == NULL)
		return NULL;

	Node* temp = this;
	while(temp->leftSibling)
		temp = temp->leftSibling;
	return temp;
}

Node* Node::rightMostSibling()
{
	if(this == NULL)
		return NULL;

	Node* temp = this;
	while(temp->rightSibling)
		temp = temp->rightSibling;
	return temp;
}

FiboHeap::FiboHeap()
{
	minRoot = NULL;
}

FiboHeap::FiboHeap(Node *root)
{
	this->minRoot = root;
	minRoot->parent = NULL;
	minRoot->children = NULL;
	minRoot->leftSibling = NULL;
	minRoot->rightSibling = NULL;
	minRoot->rank = 0;
}

FiboHeap::~FiboHeap()
{
	delete[] rootListByRank;
}

bool FiboHeap::isEmpty()
{
	return (minRoot == NULL);
}

bool FiboHeap::insertVertex(Node * node)
{
	if(node == NULL)
		return false;

	if(minRoot == NULL)
		minRoot = node;
	else
	{
		minRoot->addSibling(node);
		if(minRoot->key > node->key)
			minRoot = node;
	}
	return true;
}

Node* FiboHeap::findMin()
{
	return minRoot;
}

Node* FiboHeap::deleteMin()
{
	Node *temp = minRoot->children->leftMostSibling();
	Node *nextTemp = NULL;

	while(temp != NULL)
	{
		nextTemp = temp->rightSibling; // Save next Sibling
		temp->remove();
		minRoot->addSibling(temp);
		temp = nextTemp;
	}

	temp = minRoot->leftMostSibling();

	if(temp == minRoot)
	{
		if(minRoot->rightSibling)
			temp = minRoot->rightSibling;
		else
		{
			Node* out = minRoot;
			minRoot->remove();
			minRoot = NULL;
			return out;
		}
	}
	Node* out = minRoot;
	minRoot->remove();
	minRoot = temp;

	for(int i=0; i<100; i++)
		rootListByRank[i] = NULL;
	
	while(temp)
	{
		if(temp->key < minRoot->key)
		{
			minRoot = temp;
		}

		nextTemp = temp->rightSibling;		
		link(temp);
		temp = nextTemp;
	}

	return out;	
}

bool FiboHeap::link(Node* root)
{
	if(rootListByRank[root->rank] == NULL)
	{
		rootListByRank[root->rank] = root;
		return false;
	}
	else
	{
		Node* linkVertex = rootListByRank[root->rank];
		rootListByRank[root->rank] = NULL;
		
		if(root->key < linkVertex->key || root == minRoot)
		{
			linkVertex->remove();
			root->addChild(linkVertex);
			if(rootListByRank[root->rank] != NULL)
				link(root);
			else
				rootListByRank[root->rank] = root;
		}
		else
		{
			root->remove();
			linkVertex->addChild(root);
			if(rootListByRank[linkVertex->rank] != NULL)
				link(linkVertex);
			else
				rootListByRank[linkVertex->rank] = linkVertex;
		}
		return true;
	}
}

void FiboHeap::decreaseKey(int delta, Node* vertex)
{
	vertex->key = delta;

	if(vertex->parent != NULL) 
	{
		vertex->remove();
		minRoot->addSibling(vertex);		
	}
	if(vertex->key < minRoot->key)
		minRoot = vertex;
}

double diffclock(clock_t clock1,clock_t clock2)
{
	double diffticks=clock1-clock2;
	double diffms=(diffticks*10)/CLOCKS_PER_SEC;
	return diffms;
}
int main(int argc, char *argv[])
{
	long n;

	vector<Node*> vertices;
	vector<Edge*> edges;

	FILE *f = fopen ("dijkstra.in","r") ;
	
	fscanf(f,"%d",&n);
	
	vertices.push_back(new Node(0, 0)); 
	vertices[0]->state = LABELED;

	for(int j=1; j<n ; j++)
	{
		Node* v = new Node(j, -1);
		vertices.push_back(v);
	}
	int tail; int head; int length;
	while (fscanf(f, "%d %d %d", &tail, &head, &length) != EOF) {

		Edge* edge = new Edge(vertices[tail-1], vertices[head-1], length);
		edge->head->addIncomingEdge(edge);
		edge->tail->addOutgoingEdge(edge);
		edges.push_back(edge);
	}
	fclose(f);

	FiboHeap* heap = new FiboHeap();

	heap->insertVertex(vertices[0]);
	
	bool abort = false;
	long j = 0;
	do
	{
		Node* v = heap->deleteMin();
		
		v->state = SCANNED;
		
		for(unsigned int i = 0; i < v->outgoingEdges.size(); i++)
		{
			Edge* currentEdge = v->outgoingEdges[i];
			Node* headOfCurrentEdge = currentEdge->head;

			if(headOfCurrentEdge->state != SCANNED)
				{
				if(headOfCurrentEdge->state == UNLABELED)
				{
					headOfCurrentEdge->state = LABELED;
					headOfCurrentEdge->pred = v;
					headOfCurrentEdge->key = v->key + currentEdge->length;
					heap->insertVertex(headOfCurrentEdge);
				}
				else if(headOfCurrentEdge->key > v->key + currentEdge->length )
				{
					headOfCurrentEdge->pred = v;
					heap->decreaseKey(v->key + currentEdge->length, headOfCurrentEdge);
				}
			}
		}
	}
	
	while(!heap->isEmpty());

	f = fopen("dijkstra.out","w");
	for(int i=1; i<n;i++) {
		if (vertices[i]->key==-1)
		{
			fprintf(f,"0 ");
		}else{
			fprintf(f,"%d ", vertices[i]->key);
		}
		
	}

	fclose(f);
	return 0;
}