// FIRST (... that compiles) UPLOAD, MESSY CODE

#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

//qqq // no 'key' typename needed if u want a heap with some special structure, just overload the '<' operator
template <typename Content>
class SexyNode
{
	Content _content;
	unsigned int _id;
	unsigned int _rank;
	bool _marked;

	SexyNode<Content>* _previous;
	SexyNode<Content>* _next;
	SexyNode<Content>* _child; // first-born
	SexyNode<Content>* _parent;

	SexyNode();
	SexyNode(Content, unsigned int);
	~SexyNode();

	Content getContent();
	void insert(SexyNode<Content>*);
	void insertChild(SexyNode<Content>*);
	void remove();
	void removeChild(SexyNode<Content>*);

	template <typename> friend class SexyHeap;
};

template <typename Content>
class SexyHeap
{
	typedef SexyNode<Content>* PSexyNode;

	PSexyNode _minroot;
	unsigned int _count;
	unsigned int _maxrank;
	PSexyNode insertNode(PSexyNode);
	void merge(const SexyNode<Content>&);

public:
	SexyHeap();
	~SexyHeap();
	unsigned int getMinId();
	Content getMin();
	PSexyNode insert(Content, unsigned int);
	void removeMinimum();
	void decreaseNode(PSexyNode, Content);
	void remove(PSexyNode, Content);
};

// LAME OOP yukk ...
class SexyGraphNode

{
public:
	unsigned int _value;
	unsigned int _cost;
	SexyGraphNode* _next;

	SexyGraphNode(){};
	~SexyGraphNode(){};

	friend class SexyGraphAdjacency;
};

class SexyGraphAdjacency
{
public:

	vector<SexyGraphNode*> _nodes;
	unsigned int _nodecount;
	unsigned int _edgecount;

	SexyGraphAdjacency();
	~SexyGraphAdjacency();
	void LoadEdges(char*);
};

// main
int main()
{
	char filename[] = "dijkstra.in";
	ofstream outfile("dijkstra.out", ofstream::out);
	SexyGraphAdjacency sga;
	SexyHeap<unsigned int> sh;
	vector<unsigned int> distances;

	sga.LoadEdges(filename);
	unsigned int inf = (unsigned int)(1 << 31);
	distances.push_back(666); // >:)
	distances.insert(distances.begin() + 1, sga._nodecount + 1, inf);
	distances[1] = 0;

	vector<SexyNode<unsigned int>*> sexyheapnodes(sga._nodecount + 1);
	for (unsigned int i = 1; i <= sga._nodecount; ++i)
	{
		sexyheapnodes[i] = sh.insert(inf, i);
	}

	sh.decreaseNode(sexyheapnodes[1], 0);

	while (1)
	{
		unsigned int currentminid = sh.getMinId();
		unsigned int currentmin = sh.getMin();

		if (currentmin == (unsigned int) (1 << 31))
			break;

		sh.removeMinimum();

		//cout << "[DEBUG] Min: " << currentmin << endl;
		//cout << "[DEBUG] Id: " << currentminid << endl;

		SexyGraphNode* currentnode = sga._nodes[currentminid];

		while (currentnode)
		{
			if (distances[currentnode->_value] > distances[currentminid] + currentnode->_cost)
			{
				distances[currentnode->_value] = distances[currentminid] + currentnode->_cost;
				sh.decreaseNode(sexyheapnodes[currentnode->_value], distances[currentnode->_value]);
			}
			currentnode = currentnode->_next;
		}
	}

	for (unsigned int i = 2; i <= sga._nodecount; ++i)
	{
		if (distances[i] == (unsigned int) (1 << 31))
			outfile << "0 ";
		else
			outfile << distances[i] << " ";
	}
	outfile << endl;
}

// SexyNode
template <typename Content>
SexyNode<Content>::SexyNode()
{
}

template <typename Content>
SexyNode<Content>::SexyNode(Content c, unsigned int id): _content(c)
{
	_content = c;
	_id = id;
	_rank = 0;
	_marked = 0;

	_previous = _next = this;
	_child = 0;
	_parent = 0;
}

template <typename Content>
SexyNode<Content>::~SexyNode()
{
}

template <typename Content>
Content SexyNode<Content>::getContent()
{
	return _content;
}

template <typename Content>
void SexyNode<Content>::insert(SexyNode<Content>* newnode)
{
	if (!newnode) return; // ?!

	this->_next->_previous = newnode->_previous;
	newnode->_previous->_next = this->_next;
	this->_next = newnode;
	newnode->_previous = this;
}

template <typename Content>
void SexyNode<Content>::insertChild(SexyNode<Content>* newnode)
{
	if (!_child)
		_child = newnode;
	else
		_child->insert(newnode);
	newnode->_parent = this;
	newnode->_marked = 0;
	++_rank;
}

template <typename Content>
void SexyNode<Content>::remove()
{
	this->_previous->_next = this->_next;
	this->_next->_previous = this->_previous;
	this->_next = this->_previous = this;
}

template <typename Content>
void SexyNode<Content>::removeChild(SexyNode<Content>* oldnode)
{
	if (oldnode->_parent != this)
		return;
	if (oldnode->_next == oldnode)
	{
		if (_child != oldnode)
		{
			return;
		}
		_child = 0;
	}
	else
	{
		if (_child == oldnode)
			_child = oldnode->_next;
		oldnode->remove();
	}

	oldnode->_parent = 0;
	oldnode->_marked = 0;
	--_rank;
}

//template <typename Content>
//ostream& operator<< (ostream& out, const SexyNode<Content>& node)
//{
//	return (out << "Data: " << node._content << endl
//		<< "Has child: " <<  _child : "yes" ? "no" << endl
//		<< "Has parent: " << _parent : "yes" ? "no" << endl << endl);
//}

// SexyHeap
template <typename Content>
SexyHeap<Content>::SexyHeap(): _minroot()
{
	_minroot = 0;
	_count = 0;
	_maxrank = 0;
}

template <typename Content>
SexyHeap<Content>::~SexyHeap()
{
}

template <typename Content>
SexyNode<Content>* SexyHeap<Content>::insertNode(PSexyNode newnode)
{
	if (!_minroot)
	{
		_minroot = newnode;
	}
	else
	{
		_minroot->insert(newnode);
		if (newnode->getContent() < _minroot->getContent())
			_minroot = newnode;
	}

	return newnode;
}

template <typename Content>
unsigned int SexyHeap<Content>::getMinId()
{
	if (_minroot)
		return _minroot->_id;
	return 0; // f&*(ed
}

template <typename Content>
Content SexyHeap<Content>::getMin()
{
	if (_minroot)
		return _minroot->getContent();
	else
		return (Content) (1 << 31); // f&*(ed
}

template <typename Content>
void SexyHeap<Content>::merge(const SexyNode<Content>& second)
{
	_minroot->insert(second._minroot);
	if (!_minroot || (second._minroot && second._minroot->GetContent < _minroot->GetContent()))
	{
		_minroot = second._minroot;
	}

	_count += second._count;
}

template <typename Content>
SexyNode<Content>* SexyHeap<Content>::insert(Content newcontent, unsigned int id)
{
	++_count;

	return insertNode(new SexyNode<Content>(newcontent, id));
}

template <typename Content>
void SexyHeap<Content>::removeMinimum()
{
	if (!_minroot)
		return;

	--_count;

	// all child >> root
	if (_minroot->_child)
	{
		PSexyNode tempnode = _minroot->_child;
		do
		{
			tempnode->_parent = 0;
			tempnode = tempnode->_next;
		} while (tempnode != _minroot->_child);
		_minroot->_child = 0;
		_minroot->insert(tempnode);
	}

	// last element
	if (_minroot->_next == _minroot)
	{
		if (_count)
			return; // something is f&*ed up
		_minroot = 0;
		return;
	}

	// merge same-rank roots
	vector<PSexyNode> samerankroots(_maxrank + 1);
	fill(samerankroots.begin(), samerankroots.end(), (PSexyNode) 0);
	_maxrank = 0;
	PSexyNode currentnode = _minroot->_next;
	unsigned int currentrank;

	do 
	{
		currentrank = currentnode->_rank;

		PSexyNode currentnodelvl2 = currentnode;
		currentnode = currentnode->_next;
		while (samerankroots[currentrank]) // qqq // merge the two roots with the same rank
		{
			PSexyNode second =  samerankroots[currentrank];
			if (second->getContent() < currentnodelvl2->getContent())
				swap(second, currentnodelvl2);
			second->remove();
			currentnodelvl2->insertChild(second);
			samerankroots[currentrank++] = 0;
			if (currentrank >= samerankroots.size())
				samerankroots.push_back((PSexyNode) 0);
		}
		// keep the current root as the first of its rank in the samerankroots array
		samerankroots[currentrank] = currentnodelvl2;
	} while (currentnode != _minroot);

	// remove the current root, and calculate the new rootmin
	delete _minroot;
	_minroot = 0;

	unsigned int newmaxrank = 0;

	for (unsigned int r = 0; r < samerankroots.size(); ++r)
	{
		if (samerankroots[r])
		{
			samerankroots[r]->_next = samerankroots[r]->_previous = samerankroots[r];
			insertNode(samerankroots[r]);
			if (r > newmaxrank)
				newmaxrank = r;
		}
	}
	_maxrank = newmaxrank;
}

template <typename Content>
void SexyHeap<Content>::decreaseNode(PSexyNode changenode, Content newcontent) {
	if (!(newcontent < changenode->getContent()))
		return; // f*&ed up ...

	changenode->_content = newcontent;

	// agressiv or not
	PSexyNode parent = changenode->_parent;
	if (!parent)
	{
		if (newcontent < _minroot->getContent())
			_minroot = changenode;
		return;
	}
	else
		if (parent->getContent() < newcontent || parent->getContent() == newcontent)
			return; // heap healthy

	for (;;)
	{
		parent->removeChild(changenode);
		insertNode(changenode);

		if (!parent->_parent)
			break;
		else if (!parent->_marked)
		{
			parent->_marked = 1;
			break;
		}
		else
		{
			changenode = parent;
			parent = parent->_parent;
			continue;
		}
	}
}

template <typename Content>
void SexyHeap<Content>::remove(PSexyNode oldnode, Content minusinf)
{
	if (!(minusinf < _minroot))
		return; // f*(&ed up

	decreaseNode(oldnode, minusinf);
	removeMinimum();
}

// SexyGraphAdjacency
SexyGraphAdjacency::SexyGraphAdjacency()
{
}

SexyGraphAdjacency::~SexyGraphAdjacency()
{
}

void SexyGraphAdjacency::LoadEdges(char* from)
{
	ifstream infile(from, ifstream::in);

	infile >> _nodecount >> _edgecount;
	_nodes = vector<SexyGraphNode*>(_nodecount + 1, 0);

	for (unsigned int i = 0; i < _edgecount; ++i)
	{
		unsigned int from, to, cost;
		SexyGraphNode* tempnode = new SexyGraphNode;

		infile >> from >> to >> cost;

		tempnode->_cost = cost;
		tempnode->_value = to;
		tempnode->_next = _nodes[from];
		_nodes[from] = tempnode;
	}

	infile.close();
}