#include <algorithm>
#include <bitset>
#include <fstream>
#include <iterator>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

vector<int> d;

class comp
{
public:
	bool operator ()(int x, int y)
	{
		return d[x] > d[y];
	}
};

void main2()
{
	ifstream in("dijkstra.in");
	
	int N, M;
	in >> N >> M;
	
	vector<vector<pair<int, int> > > g(N + 1);
	d.resize(N + 1);

	for (int i = 0; i < M; i++)
	{
		int x, y, z;
		in >> x >> y >> z;

		g[x].push_back(pair<int, int>(y, z));
	}

	bitset<50001> is, was;
	priority_queue<int, vector<int>, comp> q;

	for (q.push(1), was[1] = true; !q.empty(); q.pop())
	{
		int top = q.top();
		is[top] = false;

		for (vector<pair<int, int> >::iterator i = g[top].begin(); i != g[top].end(); i++)
		{
			int first = i->first;
			int second = i->second;

			if (!was[first] || (d[first] > d[top] + second))
			{
				d[first] = d[top] + second;

				was[first] = true;

				if (!is[first])
				{
					q.push(first);

					is[first] = true;
				}
			}
		}
	}
	
	ofstream out("dijkstra.out");
	copy(d.begin() + 2, d.end(), ostream_iterator<int>(out, " "));
}