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

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);
	std::queue<int> Q;

	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));
	}
	
	std::vector<int> D(nodeCount + 1, std::numeric_limits<int>::max());
	D[1] = 0;
	Q.push(1);

	while (!Q.empty())
	{
		int s = Q.front();

		Q.pop();

		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);
			}
		}
	}

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

	out << std::endl;
}


int main()
{
	mainQueue();
}