#include<stdio.h>
long i,j,n,m,x,y,min,k;
long a[1000][1000],d[1000],s[1000];

int main(void)
{
	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++)
	if(i!=j)
	a[i][j]=32000;

	for(i=1;i<=m;i++)
	{
		scanf("%ld%ld",&x,&y);
		scanf("%ld",&a[x][y]);
	}
	for(i=2;i<=n;i++)
		d[i]=a[1][i];
	s[1]=1;
	for(i=1;i<n;i++)
	{
		min=32000;
		for(j=1;j<=n;j++)
			if(d[j]<min&&!s[j])
				{
				min=d[j];
				k=j;
				}
		s[k]=1;
		for(j=1;j<=n;j++)
			if(s[j]==0)
			if(min+a[k][j]<d[j])
				d[j]=min+a[k][j];
	}
	for(i=2;i<=n;i++)
	if(d[i]<32000)
	printf("%ld ",d[i]);
	else
	printf("0 ");
	return 0;
}