#include<stdio.h>

const long long unsigned inf= 1.e30;

#define in "file.in"
#define out "file.out"

long long unsigned m,n,a[10001][10001],i,j,k,d[50001],min,s[50001],poz,c;

int main()
{
	freopen(in,"r",stdin);
	freopen(out,"w",stdout);
	scanf("%llu%llu",&n,&m);

	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j)
				a[i][j]=inf;

	for(i=1;i<=m;i++)
	{
		scanf("%llu%llu%llu",&j,&k,&c);
		a[j][k]=c;
	}
	for(i=1;i<=n;i++)
		d[i]=a[1][i];
	s[1]=1;
	for(i=1;i<n;i++)
	{
		min=inf;
		for(j=1;j<=n;j++)
		{
			if(!s[j])
			{
				if(d[j]<min)
				{
					min=d[j];
					poz=j;
				}
			}
		}
		s[poz]=1;
		for(j=1;j<=n;j++)
		{
			if(!s[j])
			{
				if(d[j]>d[poz]+a[poz][j])
					d[j]=d[poz]+a[poz][j];
			}
		}
	}
	for(i=2;i<=n;i++)
		printf("%llu ",d[i]);
	return 0;
}