#include <cstdio>
#include <vector>
#include <utility>
using namespace std;

#define Nmax 50001
#define inf 0x3f3f3f3f

FILE *f=fopen ("dijkstra.in","r");
FILE *g=fopen ("dijkstra.out","w");

vector < pair <int,int> > G[Nmax];

int heap[Nmax], poz[Nmax],dist[Nmax], N, M, Lgheap;

void Citire (){
	int x, y, c;
	
	fscanf (f,"%d%d",&N,&M);
	
	for (int i = 1; i <= M; ++i){
		fscanf (f,"%d%d%d",&x,&y,&c);
		G[x].push_back ( make_pair (y,c) );
	}
}

void Swap (int x, int y){
	swap (heap[x] , heap[y]);
	swap (poz[heap[x]] , poz[heap[y]]);
}

void UpHeap (int nod){
	if (dist[ heap[(nod>>1)] ] < dist[ heap[nod] ]) return;
	
	Swap (nod,nod>>1);
	UpHeap (nod>>1);
}

void DownHeap (int nod){
	int st, dr;
	
	if ( (nod<<1) > Lgheap ) return;
	
	st = dist[ heap[(nod<<1)] ];
	
	if ( (nod<<1)+1 <= Lgheap ) dr = dist[ heap[(nod<<1)+1] ];
	else  dr = st + 1;
	
	if (st < dr){
		if (dist [ heap[nod] ] <= st) return;
		Swap (nod, nod<<1);
		DownHeap (nod<<1);
	}
	else{
		if (dist [ heap[nod] ] <= dr) return;
		Swap (nod, (nod<<1)+1);
		DownHeap ((nod<<1)+1);
	}
}

void init (){
	Lgheap = N;
	
	for (int i = 1; i <= N ; ++i){
		heap[i] = i;
		poz[i] = i;
		dist[i] = inf;
	}
	dist[1] = 0;
	dist[0] = -1;
	//UpHeap (start);
}

void Dijkstra (){
	int nod;
	vector < pair <int,int> > :: iterator it;
	
	for (int i = 1 ; i <= N ; ++i){
		nod = heap[1];
		Swap (1,Lgheap--);
		DownHeap (1);
		
		for (it = G[nod].begin(); it < G[nod].end(); ++it){
			if (dist[it -> first] > 1LL * dist[nod] + it -> second ){
				dist[it -> first] = 1LL * dist[nod] + it -> second;
				UpHeap (poz[it -> first]);
			}
		}
	}
}

void Afisare (){
	for (int i = 2; i <= N ;++i)
		fprintf (g,"%d ",dist[i] != inf ? dist[i] : 0);
}

int main(){
	
	Citire ();
	init ();
	Dijkstra ();
	Afisare ();
	
	return 0;
}