#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");
	
	int nodeCount, arcCount;
	in >> nodeCount >> arcCount;
	
	std::vector<std::vector<std::pair<int, int> > > graph(nodeCount + 1);
	destinations.resize(nodeCount + 1);

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

		graph[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> queue;

	for (queue.push(1), wasInHeap[1] = true; !queue.empty(); queue.pop())
	{
		int top = queue.top();
		isInHeap[top] = false;

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

			if (!wasInHeap[first] || (destinations[first] > destinations[top] + second))
			{
				destinations[first] = destinations[top] + second;

				wasInHeap[first] = true;

				if (!isInHeap[first])
				{
					queue.push(first);

					isInHeap[first] = true;
				}
			}
		}
	}
	
	std::ofstream out("dijkstra.out");
	std::copy(destinations.begin() + 2, destinations.end(), std::ostream_iterator<int>(out, " "));
}

int main()
{
	mainQueue();
}