#include<stdio.h>
#define N 50005
#define M 250005
#define C 50000000
int n,m,*a[N],*c[N],s[N],d[N],x[M],y[M],cost[M];
void citire()
{
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x[i],&y[i],&cost[i]);
		++d[x[i]];
	}
	for(i=1;i<=n;i++)
	{
		a[i]=new int[d[i]+1];
		c[i]=new int[d[i]+1];
		a[i][0]=0;
		c[i][0]=0;
	}
	for(i=1;i<=m;++i)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
		c[x[i]][++c[x[i]][0]]=cost[i];
	}
}

void alege(int &x)
{
	int min=C,j;
	for(j=1;j<=n;j++)
	{
		if((d[j]<min) && (s[j]==0))
		{
			min=d[j];
			x=j;
		}
	}
	s[x]=1;
}

void dijkstra(int x)
{
	int y;
	for(int i=1;i<=n;i++)
	{
		d[i]=C;
		s[i]=0;
	}
	d[x]=0;
	for(int i=1;i<=n;i++)
	{	
		alege(x);
		for(int j=1 ; j<=a[x][0] ; ++j)
		{
			y=a[x][j];
			if( d[x] + c[x][j] < d[y])
				d[y] = d[x] + c[x][j];
		}
	}
}

void afisare()
{
	for(int i=2;i<=n;i++)
	{
		if(d[i]==C)
			printf("0 ");
		else
			printf("%d ",d[i]);
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra(1);
	afisare();
	return 0;
}