#include <iostream>
#include <fstream>
#include <vector>
#define nmax 50005
#define inf 10000000

using namespace std;

const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";
const int MAX_HEAP_SIZE = 16384;
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 Pos[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]);
			K = fiu;
		}
	}while(fiu);
}
		
void percolate(Heap H, int N, int K)
{
	int cheie = val[H[K]];
	while(K > 1 && cheie < father(K))
	{
		val[H[K]] = val[H[father(K)]];
		K = father(K);
	}
	val[H[K]] = cheie;
}

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

int out()
{
	int r = H[1];
	//val[H[1]] = val[H[N]];
	H[1] = H[N];
	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;
	while(N > 0)
	{	
		if(pas == 1) r = 1;
		++pas;
		if(val[r] == inf)
			break;
		
		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;
		}
		
		r = out();
		if(pas == 2)
			build_heap(H, N);
		
	}
	
	for(i = 2; i <= Nr; i ++)
		if(val[i] == inf)
			fout << "0 ";
		else
			 fout << val[i] << " ";
	
	return 0;
}