#include <fstream>
#include <vector>

#define pb push_back
#define NMAX 50100

using namespace std;

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

struct nod{
	int cost, next;
};

vector<nod> Graf[NMAX];
int Heap[NMAX], heapLen, N, M, Cost[NMAX], minCalc[NMAX], minLen, Pos[NMAX];

inline void Switch(int &a, int &b)
{
	a += b;
	b = a - b;
	a -= b;
}

void heapReconstruct(int i)
{
	int l = 2*i, r = 2*i + 1, min = i;
	
	if(l < heapLen && Cost[Heap[l]] < Cost[Heap[min]])
		min = l;
	if(r < heapLen && Cost[Heap[r]] < Cost[Heap[min]])
		min = r;
	
	if (min != i)
	{
		Switch(Heap[min], Heap[i]);
		Switch(Pos[Heap[min]], Pos[Heap[i]]);
		
		heapReconstruct(min);
	}
}
inline void heapUpdate(int i)
{
	while(i > 1 && Cost[Heap[i]] < Cost[Heap[i/2]])
	{
		Switch(Heap[i], Heap[i/2]);
		Switch(Pos[Heap[i]], Pos[Heap[i/2]]);
		
		i /= 2;
	}
}

inline int heapPop(void)
{
	int Val = Heap[1];
	
	Heap[1] = Heap[heapLen];
	Pos[Heap[heapLen]] = 1;
	
	heapReconstruct(1);
		
	heapLen--;
		
	return Val;
}

void dijkstra(void)
{
	int i, nodMin, nu, cr; //nodulUrmator si costRelativ 
	
	Cost[1] = 0;
	Pos[1] = 1;
	heapLen = 1;
	Heap[1] = 1;
	minLen = 0;
	
	while (minLen != N)
	{
		nodMin = heapPop();
		
		minCalc[nodMin] = 1;
		
		for (i = 0; i < Graf[nodMin].size(); i++)
		{
			nu = Graf[nodMin][i].next;
			cr = Graf[nodMin][i].cost;
			
			if (minCalc[nu] == 0)
			{
				if (Cost[nu] == -1)
				{
					Cost[nu] = cr + Cost[nodMin];
					heapLen++;
					Pos[nu] = heapLen;
					Heap[heapLen] = nu;
					heapUpdate(heapLen);
				}
				else
				{
					if (Cost[nu] > cr + Cost[nodMin])
					{
						Cost[nu] = cr + Cost[nodMin];
						heapUpdate(Pos[nu]);
					}
				}
			}
		}
		
		minLen++;
	}
	
}

int main()
{
	int i, n1;
	nod Add;
	
	fin >>N >>M;
	
	for (i = 1; i <= M; i++)
	{
		fin >>n1 >>Add.next >>Add.cost;
		Graf[n1].pb(Add);
	}
	for (i = 1; i <= N; i++)
		Cost[i] = -1;
	
	dijkstra();	
	
	for (i = 2; i <= N; i++)
		fout <<Cost[i] <<' ';
	fout.close();
	return 0;
}