#include<stdio.h>

const long max=2500000;
struct muchie { long x,y,c;
			  } a[250001];
long n,m,d[50001];

void citire()
{   long i;
	freopen("bellmanford.in","r",stdin);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=m;i++)
	{	scanf("%ld%ld%ld",&a[i].x,&a[i].y,&a[i].c);
		if(a[i].x==1) d[a[i].y]=a[i].c;
	}
	for(i=1;i<=n;i++)
		if(d[i]==0) d[i]=max;
}

int main()
{   long i,cont=1;
	freopen("bellmanford.out","w",stdout);
	citire();
	while(cont)
	{	cont=0;
		for(i=1;i<=m;i++)
			if(d[a[i].y]>d[a[i].x]+a[i].c)
			{	d[a[i].y]=d[a[i].x]+a[i].c;
				cont=1;
			}
	}
	for(i=2;i<=n;i++)
		printf("%ld ",d[i]);
	return 0;
}