#include<cstdio>
int a[23000][23000],t[50000],viz[50000],d[50000],min,k,j,i,ok,x,y,c,m,n;

void citire()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		a[i][j]=9999;
	for(i=1;i<=m;i++){
	scanf("%d %d %d",&x,&y,&c);
	a[x][y]=c;
	}
	for(i=1;i<=n;i++){
		t[i]=1;
		d[i]=a[1][i];
	}
	
}

int main()
{
	citire();
	ok=1;t[1]=0;
	
	while (ok==1){
	min=9999;
	for(i=1;i<=n;i++)
		if(d[i]<min && viz[i]==0){
			min=d[i];
			k=i;
		}
	if (min!=9999){
		viz[k]=1;
		for(i=1;i<=n;i++)
			if(d[i]>a[k][i]+min && a[k][i]!=9999){
				d[i]=a[k][i]+min;
				t[i]=k;
			}
	}
	else ok=0;
	}
	
	for(i=2;i<=n;i++)
		if(d[i]==9999)printf("0 ");
	else printf("%d ",d[i]);
	return 0;
}