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

std::vector<int> destinations;

class Comparator
{
public:
	bool operator ()(int x, int y)
	{
		return destinations[x] > destinations[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);
	destinations.resize(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));
	}
	

	std::vector<char> isInHeap(nodeCount + 1), wasInHeap(nodeCount + 1);
	std::priority_queue<int, std::vector<int>, Comparator> Q;

	for (Q.push(1), wasInHeap[1] = true; !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 (!wasInHeap[x] || (destinations[x] > destinations[s] + y))
			{
				destinations[x] = destinations[s] + y;

				wasInHeap[x] = true;

				if (!isInHeap[x])
				{
					Q.push(x);

					isInHeap[x] = true;
				}
			}
		}
	}

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

int main()
{
	mainQueue();
}