#include<stdio.h>
#define inf 2000000000
#define dim 50010

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

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

int i,n,u,m,d[dim],Fr[dim],C[5*dim],a,b,e,nc,p;

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

int main(){
	read();
	for(i=2;i<=n;i++)
		d[i]=inf;
	
	p=1;u=1;C[1]=1;Fr[1]=1;
	
	while(p<=u){
		nc=C[p];
		c=L[nc];
		while(c){
			if((d[nc]+c->d)<d[c->nr]){
				d[c->nr]=d[nc]+c->d;
				if(!Fr[c->nr]){
					C[++u]=c->nr;
					Fr[c->nr]=1;
				}
			}
			c=c->adr;
		}
		Fr[nc]=0;
		p++;
	}
	
	for(i=2;i<=n;i++)
		fprintf(g,"%d ",d[i]);
	
	return 0;
}