#include <fstream>
#include <map>
#include <list>
#include <vector>
#include <string.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;

class Line
{
private:
	typedef std::map<unsigned int, unsigned int>	Values;

private:
	Values		values;

public:
	Line()
	{

	}

	unsigned int operator [] (unsigned int _index) const
	{
		Values::const_iterator		itValue;

		unsigned int val = INFINITE;

		itValue = values.find(_index);
		if (values.end() != itValue)
			return itValue->second;

		return val;
	}

	unsigned int & operator[](unsigned int _index)
	{
		return values[_index];
	}
}; 

class Matrix
{
private:
	typedef std::map<unsigned int, Line>		Lines;

private:
	Lines		lines;
public:
	Matrix()
	{

	}

	const Line & operator [](unsigned int _index) const
	{
		return lines.find(_index)->second;
	}

	Line & operator [](unsigned int _index)
	{
		return lines[_index];
	}
};

void dijkstra(unsigned int _currentNode, unsigned int _cost, const Graf &_graf, Matrix &_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);
	Matrix 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] == INFINITE ? 0 : distances[uIndex])<<" ";

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

	return 0;
}