#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <conio.h>
#include <iostream>
#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
{
	// QQQ BAD-SOLUTION
public:
	Content _content;
	unsigned int _rank;
	bool _marked;

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

	void insertChild(SexyNode<Content>*);
	void remove();
	void removeChild(SexyNode<Content>*);
	
	friend ostream& operator<< (ostream& out, const SexyNode<Content>& node);

	SexyNode();
	SexyNode(Content);
	~SexyNode();

	Content getContent();
	void insert(SexyNode<Content>*);
};

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>&);
	void decreaseNode(PSexyNode, Content);
	void remove(PSexyNode, Content);

public:
	Content getMin();
	PSexyNode insert(Content);
	void removeMinimum();

	SexyHeap();
	~SexyHeap();
};

const int maxn = 50001;
const int inf = 1 << 30;

FILE *in = fopen("dijkstra.in","r");//, *out = fopen("dijkstra.out","w");

struct graf
{
    int nod, cost;
    graf *next;
};

int n, m;
graf *a[maxn];
int d[maxn], h[maxn], poz[maxn], k;
SexyHeap<int> sh;

void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}

void read()
{
    fscanf(in, "%d %d", &n, &m);

    int x, y, z;
    for ( int i = 1; i <= m; ++i )
    {
        fscanf(in, "%d %d %d", &x, &y, &z);
        add(x, y, z);
    }
}

void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void dijkstra_heap()
{
    for (int i = 2; i <= n; ++i )
        d[i] = inf, sh.insert(inf);
	d[1] = 0;

    while ( k )
    {
        int min = h[1];
        swap(1, k);
        poz[ h[1] ] = 1;
        --k;

		//sh.removeMinimum();
		cout << sh.getMin() << endl;

        graf *q = a[min];

        while ( q )
        {
            if ( d[q->nod] > d[min] + q->cost )
            {
                d[q->nod] = d[min] + q->cost;

                if ( poz[q->nod] != -1 )
                    upheap( poz[q->nod] );
                else
                {
                    h[++k] = q->nod;
                    poz[ h[k] ] = k;
					sh.insert( k );
                }
            }
            q = q->next;
        }
    }
}

int main()
{
    read();
    dijkstra_heap();
	
	cout << "WTF: " << sh.getMin() << endl;
	_getch();
    return 0;
}

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

template <typename Content>
SexyNode<Content>::SexyNode(Content c): _content(c)
{
	_content = c;
	_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-_mark = 0;
	--degree;
}

template <typename Content>
ostream& operator<< (ostream& out, const SexyNode<Content>& node)
{
	return (out << "Data: " << node._content << endl
		<< "Has child: " <<  _child : "yes" ? "no" << endl
		<< "Has paren: " << _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>
Content SexyHeap<Content>::getMin()
{
	if (_minroot)
		return _minroot->getContent();
	else
		return -1;
	// qqq
}

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)
{
	++_count;

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

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
	PSeyxNode 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->_mark)
		{
			parent->_mark = 1;
			break;
		}
		else if
		{
			changenode = parent;
			parent = parent->parent;
			continue;
		}
	}
}

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

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