#include <fstream>
#include <set>
#include <vector>
#include <iostream>

#define Max_N 50003
#define oo 10000000
#define in "dijkstra.in"
#define out "djikstra.out"

using namespace std;

class DjikstraAlg
{
	private :
		int N, M, D[Max_N];
		vector < pair<int, int> > V[Max_N];
		multiset < pair<int, int> > My_Heap;

	public :
		void Read_Data()	{
			ifstream fin(in);

			fin >> N >> M;
			for(int x, y, dist, i = 1; i <= M; ++i)	{
				fin >> x >> y >> dist;
				V[x].push_back({ y, dist });
			}
		}

		void Compute()	{
			for (int i = 2; i <= N; ++i)	D[i] = oo;
			
			D[1] = 0;
			My_Heap.insert({ 0, 1 });
			
			while (!My_Heap.empty())	{
				pair < int, int > nod = *My_Heap.begin();
				My_Heap.erase(nod);

				for (vector< pair <int, int > > :: iterator it = V[nod.second].begin(); it != V[nod.second].end(); ++it)	{
					if (nod.first + it->second < D[it->second])	{
						My_Heap.erase({ D[it->second], it->second });
						D[it->second] = nod.first + it->second;
						My_Heap.insert({ D[it->second], it->first });
					}
				}
			}
		}

		void WriteData()	{
			ofstream fout(out);

			for (int i = 2; i <= N; ++i)	cout << (D[i] == oo ? 0 : D[i]) << ' ';
		}

};

int main()
{
	DjikstraAlg obj;

	obj.Read_Data();
	obj.Compute();
	obj.WriteData();

	return 0;
}