#include <fstream>
#include <vector>
#include <map>

class Cost
{
private:
	unsigned int cost;

public:
	Cost() : cost(0xFFFF0000)
	{

	}

	Cost(unsigned int _cost) : cost(_cost)
	{

	}

	operator unsigned int & ()
	{
		return cost;
	}
};

template<typename T>
class Line
{
private:
	typedef std::map<unsigned int, T>		Nodes;

private:
	Nodes		nodes;

public:
	Line()
	{

	}

	const T & operator [](unsigned int _uIndex) const
	{
		return nodes[_uIndex];
	}

	T & operator [](unsigned int _uIndex)
	{
		return nodes[_uIndex];
	}
};

template<typename T>
class Matrix
{
private:
	typedef std::vector<Line<T> >		Lines;

private:
	Lines		lines;

public:
	Matrix(unsigned int _N)
	{
		while(_N)
		{
			lines.push_back(Line<T>());
			--_N;
		}
	}

	const Line<T> & operator [](unsigned int _uIndex) const
	{
		return lines[_uIndex - 1];
	}

	Line<T> & operator [](unsigned int _uIndex)
	{
		return lines[_uIndex - 1];
	}
};

class Graf : public Matrix<Cost>
{
private:
	typedef std::vector<bool>		Visited;

private:
	unsigned int N;
	//Visited	visited;

public:
	Graf(int _N) : Matrix<Cost>(_N), N(_N)
	{
		/*for (unsigned int uIndex = 1; uIndex <= N; ++ uIndex)
			visited.push_back(false);*/
	}

	void dijkstra(unsigned int _source, unsigned int _x, unsigned int _c)
	{
		//visited[_x - 1] = true;

		for (unsigned int uIndex = 1; uIndex <= N; ++ uIndex)
		{
			if (uIndex != _x)
			{
				Cost &sourceCost = (*this)[_source][uIndex];
				Cost &localCost = (*this)[_x][uIndex];

				if (_c + localCost <= sourceCost/* && !visited[_x -1]*/)
				{
					(unsigned int&)sourceCost = _c + localCost;
					
					this->dijkstra(_source, uIndex, _c + localCost);
				}
			}
		}
	}

	unsigned int getMinLength(unsigned int _x, unsigned int _y)
	{
		this->dijkstra(_x, _x, 0);

		return (*this)[_x][_y];
	}
};

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);

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

		graf[x][y] = Cost(c);
	}

	for (unsigned int uIndex = 2; uIndex < N; ++ uIndex)
		fout<<graf.getMinLength(1, uIndex)<<" ";

	fout<<graf.getMinLength(1, N);

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

	return 0;
}