#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];
char ss[32];
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
{
		fgets(ss,32,stdin);
		l=strlen(ss)-1;
		a=b=c=j=0;
		while (ss[j]!=' ')
			a=a*10+ss[j++]-48;

		j++;
		while (ss[j]!=' ')
			b=b*10+ss[j++]-48;

		j++;
		while (j<l)
			c=c*10+ss[j++]-48;
	x[i]=a;
	y[i]=b;
	z[i]=c;
//		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;
}