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

int main()
{
	std::ifstream in("dijkstra.in");
	std::ofstream out("dijkstra.out");

	std::vector<std::vector<int> > arcs, graph;
	
	// Read the number of nodes and arcs.
	int nodeCount, arcCount;
	in >> nodeCount >> arcCount;

	// Make sure we have enough space.
	graph.resize(arcCount);
	arcs.resize(arcCount);

	for (int i = 1; i <= arcCount; i++)
	{
		int sourceNode, targetNode, arcLength;
		in >> sourceNode >> targetNode >> arcLength;

		graph[sourceNode].push_back(targetNode);
		arcs[sourceNode].push_back(arcLength);
	}

	std::vector<int> distances(nodeCount + 1, std::numeric_limits<int>::max());
	std::vector<std::pair<int, int> > targets;
	targets.push_back(std::make_pair(0, 1));

	while (targets.size() > 0)
	{
		int origDist = (*targets.begin()).first;
		int origNode = (*targets.begin()).second;

		targets.erase(targets.begin());

		for (int i = 0; i < static_cast<int>(graph[origNode].size()); i++)
		{
			int arc = arcs[origNode][i];
			int node = graph[origNode][i];

			if (distances[node] > origDist + arc)
			{
				distances[node] = origDist + arc;
				
				targets.push_back(std::make_pair(distances[node], node));
			}
		}
	}

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