#include<stdio.h>
const int inf=10000000;
const int N=1001;
int n, d[N], ap[N],a[N][N], c[N][N],x;
void citire();
int min();
void dijkstra(int);
void dijkstra(int x){
	int i,j,y;
	for(i=1;i<=n;++i)
		d[i]=inf;
	d[x]=0;
	for(i=1;i<=n;++i){
		x=min();
		ap[x]=1;
		for(j=1;j<=a[x][0];++j){
			y=a[x][j];
			if(d[y]>d[x]+c[x][j])
				d[y]=d[x]+c[x][j];
		}
	}
}
int min(){
	int m, dm=inf;
	for(int i=1;i<=n;++i)
		if(dm>d[i]&&ap[i]==0){
			dm=d[i];
			m=i;
		}
	return m;
}
void citire(){
	int m,x,y,z;
	scanf("%d%d", &n, &m);
	while(m--){
		scanf("%d%d%d", &x, &y, &z);
		a[x][++a[x][0]]=y;
		c[x][++c[x][0]]=z;
	}
}
int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra(1);
	for(int i=2; i<=n;++i){  
		if(d[i]==inf)  
			printf("%d ", 0);  
		else 
			printf("%d ", d[i]);  
	}  
	return 0;
}