#include<stdio.h>
#define PLM 50000000
//MUIE PALI :>
FILE *f1,*f2;
long a,b,c,n1,n2,i,j,k,N,M,v,ok;
struct muchie{
	int unu;
	int doi;
	int val;
};
int d[50000];
muchie m[250000];
void bell(){
	d[1]=0;
	for(i=1;i<N;i++){
		ok=0;
		for(j=1;j<=M;j++){
			if(d[m[j].doi]>d[m[j].unu]+m[j].val){
				d[m[j].doi]=d[m[j].unu]+m[j].val;
				ok=1;
			}
		}
		if(!ok){
			return;
		}
	}
}
int main(){
	f1=fopen("dijkstra.in","r");
	f2=fopen("dijkstra.out","w");
	fscanf(f1,"%ld%ld",&N,&M);
	for(i=1;i<=N;fscanf(f1,"%d%d%d",&m[i].unu,&m[i].doi,&m[i].val),d[i]=PLM,i++);
	bell();
	for(i=2;i<=N;i++){
		if(d[i]!=PLM){
			fprintf(f2,"%d ",d[i]);
		}
		else{
			fprintf(f2,"0 ");
		}
	}
	return 0;
}