#include <deque>
#include <fstream>
#include <iterator>
#include <limits>
#include <queue>
#include <vector>
#include <utility>

std::vector<int> D;

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

void mainQueue()
{
	std::ifstream in("dijkstra.in");
	std::ofstream out("dijkstra.out");
	
	int nodeCount, arcCount;
	in >> nodeCount >> arcCount;
	
	std::vector<std::vector<std::pair<int, int> > > nodeMatrix(nodeCount + 1);

	for (int i = 0; i < arcCount; i++)
	{
		int source, destination, length;
		in >> source >> destination >> length;

		nodeMatrix[source].push_back(std::pair<int, int>(destination, length));
	}
	
	D.resize(nodeCount + 1);
	std::fill(D.begin(), D.end(), std::numeric_limits<int>::max());
	D[1] = 0;

	std::priority_queue<int, std::deque<int>, Comparator> Q;

	for (Q.push(1); !Q.empty(); Q.pop())
	{
		int s = Q.top();

		for (std::vector<std::pair<int, int> >::iterator i = nodeMatrix[s].begin(); i != nodeMatrix[s].end(); i++)
		{
			int x = i->first;
			int y = i->second;

			if (D[x] > D[s] + y)
			{
				D[x] = D[s] + y;

				Q.push(x);
			}
		}
	}

	std::copy(D.begin() + 2, D.end(), std::ostream_iterator<int>(out, " "));

	//for (int i = 2; i <= nodeCount; ++i)
	//	out << (D[i] == std::numeric_limits<int>::max() ? 0 : D[i]) << ' ';
}


int main()
{
	mainQueue();
}