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

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

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

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

	// Populate the vectors with the nodes and arcs.
	for (short i = 1; i <= arcCount; i++)
	{
		short sourceNode, targetNode, arcLength;
		in >> sourceNode >> targetNode >> arcLength;

		graph.at(sourceNode).push_back(targetNode);
		arcs.at(sourceNode).push_back(arcLength);
	}

	std::vector<short> distances(nodeCount + 1, std::numeric_limits<short>::max());
	std::set<std::pair<short, short> > targets;

	targets.insert(std::make_pair(0, 1));

	while (targets.size() > 0)
	{
		short val = (*targets.begin()).first;
		short x = (*targets.begin()).second;
		targets.erase(*targets.begin());

		for (short i = 0; i < static_cast<short>(graph.at(x).size()); i++)
		{
			if (distances.at(graph.at(x).at(i)) > val + arcs.at(x).at(i))
			{
				distances.at(graph.at(x).at(i)) = val + arcs.at(x).at(i);
				
				targets.insert(std::make_pair(distances.at(graph.at(x).at(i)), graph.at(x).at(i)));
			}
		}
	}

	// Output the results.
	for (short i = 2; i <= nodeCount; i++)
		out << ((distances.at(i) == INT_MAX) ? 0 : distances.at(i)) << ' ';
}