#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define MAX_N			50100
#define INFINITE		((unsigned int)0x3F3F3F3F)

class CompByCost
{
public:
	bool operator ()(const std::pair<unsigned int, unsigned int> &_pair1, const std::pair<unsigned int, unsigned int> &_pair2) const
	{
		return _pair1.second < _pair2.second;
	}
};

typedef std::vector<std::pair<unsigned int, unsigned int> > Neighbours;
typedef std::priority_queue<std::pair<unsigned int, unsigned int>, std::vector<std::pair< unsigned int, unsigned int > >, CompByCost > Set;

Neighbours				graf[MAX_N];
unsigned int			distances[MAX_N];

void dijkstra(unsigned int _currentNode)
{
	Set		set;

	set.push(std::make_pair(_currentNode, 0));
	distances[_currentNode] = 0;

	while(set.size())
	{
		Neighbours::const_iterator itNode;

		unsigned int currentNode = set.top().first;
		unsigned int cost = set.top().second;

		set.pop();

		for (itNode = graf[currentNode].begin(); graf[currentNode].end() != itNode; ++ itNode)
		{
			unsigned int totalCost = itNode->second + cost;

			if (totalCost < distances[itNode->first])
			{
				distances[itNode->first] = totalCost;
				set.push(std::make_pair(itNode->first, totalCost));
			}
		}
		
	}
}

int main()
{
	unsigned int x, y, c;
	unsigned int N, M;

	std::ifstream fin("dijkstra.in");
	std::ofstream fout("dijkstra.out");

	fin>>N>>M;

	memset(&distances[0], INFINITE, (N + 2) * sizeof(unsigned int));

	for (unsigned int uIndex = 0; uIndex < M; ++ uIndex)
	{
		fin>>x>>y>>c;

		graf[x].push_back(std::make_pair(y, c));
	}

	dijkstra(1);

	for (unsigned int uIndex = 2; uIndex <= N; ++ uIndex)
		fout<<(distances[uIndex] == INFINITE ? 0 : distances[uIndex])<<" ";

	fin.close();
	fout.close();

	return 0;
}