#include <fstream>
#include <map>
#include <list>
#include <vector>
#include <stdlib.h>

#define INFINITE		((unsigned int)0x3F3F3F3F)

typedef std::map<unsigned int, unsigned int>		Cost;
typedef std::map<unsigned int, Cost>				Costs;
typedef std::vector<unsigned int>					Distances;

typedef std::list<unsigned int>						Neighbours;

typedef std::vector<Neighbours>		Graf;

void dijkstra(unsigned int _currentNode, unsigned int _cost, const Graf &_graf, Costs &_costs, Distances &_distances)
{
	if (_cost < _distances[_currentNode])
	{
		Neighbours::const_iterator		itNode;

		_distances[_currentNode] = _cost;

		for (itNode = _graf[_currentNode].begin(); _graf[_currentNode].end() != itNode; ++ itNode)
			dijkstra(*itNode, _cost + _costs[_currentNode][*itNode], _graf, _costs, _distances);
	}
}

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

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

	fin>>N>>M;

	Graf graf(N + 1);
	Distances distances(N + 1);
	Costs costs;

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

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

		costs[x][y] = c;
		graf[x].push_back(y);
	}

	dijkstra(1, 0, graf, costs, distances);

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

	fout<<distances[N];

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

	return 0;
}