#include <stdio.h>
int min,x[5005][5005],c,v[5005],d[5005],prev[5005];
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int n,m,i,j,a,b;
	scanf("%ld %ld",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%ld%ld%d",&a,&b,&c);
		x[a][b]=c;
	}
	for (i=2;i<=n;i++)
	{
		d[i]=2000000000;
		prev[i]=-1;
	}
	d[1]=0;
	for (i=1;i<=n;i++)
	{
		min=2000000000;
		for (j=1;j<=n;j++)
			if (d[j]<min&&!v[j])
			{
				min=d[j];
				c=j;
			}
		v[c]=1;
		for (j=1;j<=n;j++)
			if (x[c][j]&&!v[j]&&d[c]+x[c][j]<d[j])
				d[j]=d[c]+x[c][j];
	}
	for (i=2;i<=n;i++)
		printf("%d ",d[i]);
	printf("\n");
	return 0;
}