#include<stdio.h>
FILE *f,*g;
int d[50001],min,n,m,s,c[50001][50001],M[50001];
int main()
{
	f=fopen("dijkstra.in","r");
	g=fopen("dijkstra.out","w");
	fscanf(f,"%d%d",&n,&m);
	register int i,j;
	for(i=0;i<=n;++i)
		for(j=0;j<=n;++j)
			c[i][j]=999999999;
	int a,b,d;
	for(i=0;i<m;++i)
	{
		fscanf(f,"%d%d%d",&a,&b,&d);
		c[a][b]=d;
	}
	M[1]=1;
	for(i=1;i<=n;++i)
		d[i]=c[1][i];
	for(i=0;i<n-1;++i)
	{
		min=999999999;
		for(j=1;j<=n;++j)
			if(min>d[j] && M[j]==0)
			{
				min=d[j];
				a=j;
			}
		M[a]=1;
		for(j=1;j<=n;++j)
			if(M[j]==0 && d[j]>d[a]+c[a][j])
				d[j]=d[a]+c[a][j];
	}
	for(i=2;i<=n;++i)
		fprintf(g,"%d ",d[i]);
	fclose(f);
	fclose(g);
}