#include<stdio.h>
#define dim 50010

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

int P[dim],dh,n,m,i,a,b,d,min,p_min,dist[dim];

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

struct heap{
	int nod;
	int dist;
}H[dim],aux;

void up(int x){
	int c=x;
	int p=x/2;
	
	while(p){
		if(H[p].dist>H[c].dist){
			aux=H[p];
			H[p]=H[c];
			H[c]=aux;
			P[H[p].nod]=p;
			P[H[c].nod]=c;
			c=p;
			p=c*2;
		}
		else
			break;
	}
}


void down(int x){
	int p=x;
	int c=2*x;
	while(c<=dh){
		if((c+1)<=dh&&(H[c+1].dist<H[c].dist))
			c++;
		if(H[p].dist>H[c].dist){
			aux=H[p];
			H[p]=H[c];
			H[c]=aux;
			P[H[p].nod]=p;
			P[H[c].nod]=c;
			p=c;
			c=2*c;
		}
		else
			break;
	}
}


void read(){
	nod *p;
	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 main(){
	nod *c;
	read();
	
	H[++dh].nod=1;
	P[1]=1;
	
	while(dh){
		min=H[1].dist;
		p_min=H[1].nod;
		H[1]=H[dh];
		dh--;
		down(1);
		c=L[p_min];
		
		dist[p_min]=min;
		
		while(c){
			if(!P[c->nr]){
				H[++dh].nod=c->nr;
				H[dh].dist=(min+c->d);
				P[c->nr]=dh;
				up(dh);
			}
			else{
				if(H[P[c->nr]].dist>(min+c->d)){
					H[P[c->nr]].dist=(min+c->d);
					up(P[c->nr]);
				}
			}
			c=c->adr;
		}
	}
	
	for(i=2;i<=n;i++)
		fprintf(g,"%d ",dist[i]);
	return 0;
}