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

int min,p_min,n,m,a,b,i,D[dim],Fr[dim],d;

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

int main(){
	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;
	}
	for(i=2;i<=n;i++)
		D[i]=inf;
	m=n;
	while(m){
		min=inf;
		for(i=1;i<=n;i++){
			if(D[i]<min&&!Fr[i]){
				min=D[i];
				p_min=i;
			}
		}
		Fr[p_min]=1;
		c=L[p_min];
		while(c){
			if(D[c->nr]>(min+(c->d)))
				D[c->nr]=min+(c->d);
			c=(c->adr);
		}
		m--;
	}
	for(i=2;i<=n;i++)
		fprintf(g,"%d ",D[i]);
	return 0;
}