#include<fstream>
#define NMAX 50001
#define inf 1<<30

using namespace std;

struct nod {
	
	int y;
	int c;
	nod* u;
};

int n,m,dim;
int D[NMAX];
int H[NMAX];
int P[NMAX];
nod *A[NMAX];

void ADD( nod*& L, int catre, int cost){
	
	nod* q = new nod;
	q->u = L;
	q->y=catre;
	q->c=cost;
	L=q;
}
	

void swap( int &a, int&b){
	
	int aux = a;
	a=b;
	b=aux;
}

void up(int poz){
	int t=poz>>1;
	
	while( poz > 1 && D[ H[poz] ] < D[ H[t] ] ){
		swap( H[poz] , H[t] );
		P[H[poz]]=poz;
		P[H[t]]=t;
		poz = t;
		t>>=1;
	}
		
}

void down( int poz){
	int fs,fd;
	
	for(;;){
		fs = poz<<1;
		if( fs>dim) break;
		fd = fs+1;
		if( fd <=dim && D[H[fd]] < D[H[fs]]) fs=fd;
		if( D[H[poz]] < D[H[fs]]) break;
		
		swap( H[poz], H[fs]);
		P[H[poz]]=poz;
		P[H[fs]]=fs;
		poz = fs;
	}
}

void data(){
	int x,y,c;
	ifstream in("dijkstra.in");
	
	in>>n>>m;
	for( ; m-- ; ){
		in>>x>>y>>c;
		ADD( A[x],y,c );
	}
}
		
void init(){
	
	int i;
	for(i=1;i<=n;i++){ D[i]=inf; P[i]=-1; }
	D[1]=0;
	H[1]=1;
	P[1]=1;
	dim=1;
}

void dijkstra(){
	
	init();
	int min;
	
	while( dim ) {
		
		min = H[1];
		
		swap( H[1], H[dim--] );
		P[H[1]] = 1;
		down( 1 );
		
		nod* q = new nod;
		q = A[min];
		
		for( ; q ; q=q->u ){
			
			if( D[q->y] > D[min] + q->c ) D[q->y] = D[min] + q->c;
			
			if( P[q->y] != -1 ) up( P[q->y] );
			else{
				
				H[ ++dim ] = q->y;
				P[ H[dim] ] = dim;
				up(dim);
			}
		}
	}
}
				
void print(){
	
	ofstream out("dijkstra.out");
	int i;
	
	for(i=2;i<=n;i++) out<<(D[i]==inf?0:D[i])<<" ";
}

int main(){
	
	data();
	
	dijkstra();
	
	print();
	
	return 0;
}