#include<stdio.h>
#define dim 50010
#define inf 2000000000
FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");

int i,k,n,m,poz,dist,q,P[dim],D[dim],Fr[dim];

struct nod{
	int nr;
	int d;
	nod *adr;
}*p,*L[dim],*c;

struct heap{
	int d;
	int p;
}H[dim],aux;

void read(){
	int a,b,d;
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%d%d%d",&a,&b,&d);
		p=new nod;
		p->nr=b;
		p->d=d;
		p->adr=L[a];
		L[a]=p;
	}
}

int left_son(int e){
	return 2*e;
}

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

int father(int e){
	return e/2;
}

void update(int e){
	int a,b,aux1;
	while(1){
		a=left_son(e);
		b=right_son(e);
		if(a<=k&&H[a].d<H[e].d){
			q=a;
			if(b<=k&&H[b].d<H[a].d){
				q=b;
			}
		}
		else if(b<=k&&H[b].d<H[e].d){
			q=b;
		}
		else
			break;
		aux1=P[H[q].p];P[H[q].p]=P[H[e].p];P[H[e].p]=aux1;
		aux=H[q];H[q]=H[e];H[e]=aux;e=q;
	}
	
}

void urca(int x){
	int aux1;
	while(x>1&&H[x].d<H[father(x)].d){
		aux=H[x];H[x]=H[father(x)];H[father(x)]=aux;
		aux1=P[H[x].p];P[H[x].p]=P[H[father(x)].p];P[H[father(x)].p]=aux1;
		x=father(x);
	}
}

int main(){
	read();
	H[1].p=1;P[1]=1;
	for(i=2;i<=n;i++)
		H[i].d=inf,H[i].p=i,P[i]=i;
	k=n;
	while(k){
		poz=H[1].p;
		dist=H[1].d;
		D[poz]=dist;
		c=L[poz];
		while(c){
			if(dist+(c->d)<H[P[c->nr]].d){
				H[P[c->nr]].d=dist+(c->d);
				urca(P[c->nr]);
			}
			c=(c->adr);
		}
		H[1]=H[k];
		k--;
		update(1);
	}
	for(i=2;i<=n;i++)
		fprintf(g,"%d ",D[i]);
	delete p,c,L;
	return 0;
}