#include<stdio.h>
#define pinf 10000
int s[1000], d[1000], t[1000], mat[1000][1000],m,n,a,b,c,r,min;
void citire(){
	
	freopen("dijkstra.in", "r", stdin);
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(i==j)
				mat[i][j]=0;
			else
				mat[i][j]=pinf;
	for (int i=1;i<=m; ++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		mat[a][b]=c;
	}
}

int dijkstra(int r){
	for(int i=1;i<=n;++i){
		d[i]=pinf;
		t[i]=0;
		s[i]=0;
	}
	d[r]=0;
	t[r]=0;
	r=0;
	for(int i=1;i<=n;++i){
		min=pinf;
		for(int j=1;j<=n;++j){
			if((d[j]<min)&&(s[j]==0)){
				min=d[j];
				r=j;
			}
		}
		s[r]=1;
		for(int j=1;j<=n;++j)
			if(d[j]>d[r]+mat[r][j])
			{
				d[j]=d[r]+mat[r][j];
				t[j]=r;
			}
	}
}
void afisare(){
	freopen("dijkstra.out", "w", stdout);
	for(int i=2;i<=n;++i)
		printf("%d ",d[i]);
}
int main(){
	citire();
	dijkstra(1);
	afisare();
	return 0;
}