#include<stdio.h>
#define inf 2000000000
#define NMAX 50005
#define MMAX 250005
int a,b,c,i,j,n,m,x[MMAX],y[MMAX],z[MMAX],p,d[NMAX];
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
		scanf("%d%d%d",&x[i],&y[i],&z[i]);
	for (i=2;i<=n;i++)
		d[i]=inf;
	p=1;
	i=1;
	while (i<n&&p)
	{
		p=0;
		for (j=1;j<=m;++j)
		{
			a=x[j];
			b=y[j];
			c=z[j];
			if (d[b]>d[a]+c)
			{
				d[b]=d[a]+c;
				p=1;
			}
		}
		i++;

	}
	for (i=2;i<=n;i++)
		if (d[i]!=inf)
			printf("%d ",d[i]);
		else
			printf("0 ");
	printf("\n");
	return 0;
}