#include <iostream>
#include <fstream>
#include <vector>
#define nmax 50005
#define inf 1<<30

using namespace std;

const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";
const int MAX_HEAP_SIZE = 50006;
typedef int Heap[MAX_HEAP_SIZE];

ifstream fin(iname);
ofstream fout(oname);

int N, M, x, y, c, i, Nr;
vector <pair<int, int> > Nod[nmax];
int poz[nmax], val[nmax];
Heap H;

inline int father(int nod)
{
	return nod/2;
}

inline int left_son(int nod)
{
	return nod * 2;
}

inline int right_son(int nod)
{
	return nod * 2 + 1;
}

inline int min(int nod)
{
	return val[H[1]];
}

void sift(Heap H, int N, int K)
{
	int fiu;
	do
	{
		fiu = 0;
		if(left_son(K) <= Nr)
		{
			fiu = left_son(K);
			if(val[H[left_son(K)]] > val[H[right_son(K)]] && right_son(K) <= Nr)
				fiu = right_son(K);
		}
		if(val[H[K]] <= val[H[fiu]])
			fiu = 0;
		if(fiu)
		{
			//swap(val[H[K]], val[H[fiu]]);
			swap(H[K], H[fiu]);
			swap(poz[H[K]], poz[H[fiu]]);
			K = fiu;
		}
	}while(fiu);
}
		
void percolate(Heap H, int N, int K)
{
	int cheie = H[K];
	while(K > 1 && cheie < val[H[father(K)]])
	{
		H[K] = H[father(K)];
		poz[H[father(K)]] = K;
		K = H[father(K)];

	}
	poz[cheie] = K;
	H[K] = cheie;
}

void build_heap(Heap H, int N)
{
	for(i = N/2  ; i > 0; i --)
		sift(H, N, i);
}

int out()
{
	int r = H[1];
	//val[H[1]] = val[H[N]];
	H[1] = H[N];
	poz[H[N]] = 1;
	sift(H, N , 1);
	N --;
	return r;
}

int main()
{
	fin >> N >> M;
	Nr = N;
	for(i = 1; i <= M; i ++)
	{
		fin >> x >> y >> c;
		Nod[x].push_back(make_pair(y, c));
	}
	
	for(i = 1; i <= N; i ++)
		val[i] = inf;
	val[1] = 0;
	
	for(i = 1; i <= N; i ++)
		H[i] = i;
	int pas = 0;
	++ pas;
	int r = 0;
	for(i = 1; i <= N; i ++)
		poz[H[i]] = i;
	while(N > 0)
	{	
		if(pas == 1) r = 1;
		++pas;
		if(val[r] == inf)
			out();
		
		for(vector<pair<int, int> >::iterator it = Nod[r].begin(); it != Nod[r].end(); ++it)
		{
			if(val[r] + it->second < val[it->first])
			{
				val[it->first] = val[r] + it->second;
				percolate(H, N, poz[it->first]);
			}
		}
		
		r = out();
		
		//build_heap(H, N);
		
	}
	
	for(i = 2; i <= Nr; i ++)
		if(val[i] == inf)
			fout << "0 ";
		else
			 fout << val[i] << " ";
	
	return 0;
}