#include<stdio.h>
#include<values.h>
long a[10000][10000],n,m,d[50000],s[50000];
FILE *f;

void init ()
	{
	long i,j;
	for (i=1;i<=n;++i)
		{
		d[i]=MAXLONG;
		for (j=1;j<=n;++j)
			a[i][j]=MAXLONG;
		}
	}

void read ()
	{
	f=fopen("dijkstra.in","r");
	fscanf(f,"%ld%ld",&n,&m);
	init ();
	long i,x,y,c;
	for (i=1;i<=m;++i)
		{
		fscanf(f,"%ld%ld%ld",&x,&y,&c);
		a[x][y]=c;
		}
	fclose(f);
	}

void solve ()
	{
	long i,j,min,poz;
	s[1]=1;
	d[1]=0;
	for (i=2;i<=n;++i)
		if (a[1][i]<MAXLONG)
			{
			d[i]=a[1][i];
			//t[i]=1;
			}
	for (i=1;i<=n-1;++i)
		{
		min=MAXLONG;
		for (j=2;j<=n;++j)
			if (d[j]<min && !s[j])
				{
				min=d[j];
				poz=j;
				}
		s[poz]=1;
		for (j=1;j<=n;++j)
			if (a[poz][j]!=MAXLONG&&d[j]>d[poz]+a[poz][j])
				{
				d[j]=d[poz]+a[poz][j];
				//t[j]=poz;
				}
		}
	}

void write ()
	{
	f=fopen("dijkstra.out","w");
	long i;
	for (i=2;i<=n;++i)
		fprintf(f,"%ld ",d[i]);
	fclose(f);
	}

int main ()
{
read ();
solve ();
write ();
return 0;
}