#include<stdio.h>
#include<vector>
#define INF 1 << 30
#define maxN 50005
using namespace std;

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

int N,M,i,x,y,D[maxN],Poz[maxN],Sol[maxN];
int L,H[maxN];

struct mch{
	int nod;
	int cst;
}aux;

vector<mch>A[maxN];

void urca(int poz){
	while ( poz > 1 && D[ H[poz/2] ] > D[ H[poz] ] ){
		swap(H[poz],H[poz/2]);
		swap(Poz[H[poz]],Poz[H[poz/2]]);
		poz = poz >> 1;
	}
}

void coboara(int x){
	int y = -1;
	
	while ( x != y ){
		y = x;
		if ( (y << 1) <= L && D[H[ y << 1 ]] < D[H[ x ]] )
			x = y << 1;
		if ( (y << 1) + 1 <= L && D[H[(y<<1)+1]] < D[H[ x ]] )
			x = ( y << 1 ) + 1;
		swap(H[x],H[y]);
		swap(Poz[H[x]],Poz[H[y]]);
	}
	
}

void addheap(int x){
	H[++L] = x;
	Poz[x] = L;
	urca(L);
}

int extrage(int poz){
	Sol[H[poz]] = D[H[poz]];
	
	int nod = H[poz];
	int vcn;
	
	for ( int j = 0 ; j < A[nod].size() ; ++j ){
		vcn = A[nod][j].nod;
		if ( D[vcn] > D[nod] + A[nod][j].cst ){
			D[vcn] = D[nod] + A[nod][j].cst;
		}
	}
	
	swap(H[poz],H[L]);
	swap(Poz[H[poz]],Poz[H[L]]);
	--L;
	coboara(1);
	
	Poz[nod] = 0;
	D[nod] = -1;
	
	return nod;
}

int main () {
	fscanf(f,"%d %d",&N,&M);
	for ( i = 1 ; i <= M ; ++i ){
		fscanf(f,"%d %d %d",&x,&aux.nod,&aux.cst);
		A[x].push_back(aux);
	}
	
	for ( i = 2 ; i <= N ; ++i )
		D[i] = INF;
	
	H[++L] = 1;
	Poz[1] = L;
	
	extrage(1);
	
	for ( i = 2 ; i <= N ; ++i ){
		addheap(i);
	}
	
	for ( i = 1 ; i < N ; ++i ){
		int nd = extrage(1);
		
		for ( int j = 0 ; j < A[nd].size() ; ++j ){
			if ( Poz[A[nd][j].nod] )
				urca( Poz[A[nd][j].nod] );
		}
	}
	
	for ( i = 2 ; i <= N ; ++i ){
		if ( Sol[i] == INF )
			fprintf(g,"0 ");
		else
			fprintf(g,"%d ",Sol[i]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}