#include<stdio.h>
#define INF 1000000113
int n,m,*a[50113],*b[50113],d[50113];
bool s[50113];
struct muchie{
	int x,y,c;
} v[250113];
void citire(){
	int x,y,c;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
		++d[v[i].x];
	}
	for(int i=1;i<=n;++i){
		a[i]=new int[d[i]+1];
		b[i]=new int[d[i]+1];
		a[i][0]=b[i][0]=0;
	}
	for(int i=0;i<m;++i){
		x=v[i].x;
		y=v[i].y;
		c=v[i].c;
		a[x][++a[x][0]]=y;
		b[x][++b[x][0]]=c;
	}
	d[1]=0;
	for(int i=2;i<=n;++i)
		d[i]=INF;
}
void dijkstra(){
	int x,y,c,i,j,min;
	s[1]=true;
	x=1;
	for(i=1;i<n;++i){
		//pentru vecinii lui x incerc sa imbunatatesc d
		for(j=1;j<=a[x][0];++j){
			y=a[x][j];
			c=b[x][j];
			if(d[x]+c<d[y])
				d[y]=d[x]+c;
		}
		//aleg urmatorul x
		min=INF;
		for(j=2;j<=n;++j)
			if(!s[j] && d[j]<min){
				x=j;
				min=d[j];
			}
		s[x]=true;
	}
}
void afisare(){
	for(int i=2;i<=n;++i)
		printf("%d ",d[i]==INF ? 0 : d[i]);
}
int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra();
	afisare();
	return 0;
}