#include<stdio.h>
#include<stdlib.h>
#define oo  50005
#define dim 50005
using namespace std;

int n,m,*A[dim],d[dim],min,x,y,c,x0,i,*C[dim],j;
short int viz[dim],ok;

int main()
{
	FILE *f=fopen("dijkstra.in","r"), *g=fopen("dijkstra.out","w");
	
fscanf(f,"%d %d ",&n,&m);
x0=1;

for(i=1;i<=n;i++)
{
	A[i]=(int*) realloc(A[i], sizeof(int));
	A[i][0]=0;
	C[i]=(int*) realloc(C[i], sizeof(int));
	C[i][0]=0;
}

for(i=1;i<=m;i++)
{ 	
	fscanf(f,"%d %d %d",&x,&y,&c);
	
	A[x][0]++;
	A[x]=(int*)realloc(A[x],(A[x][0]+1)*sizeof(int));
	A[x][A[x][0]]=y;
	
	
	C[x][0]++;
	C[x]=(int*)realloc(C[x],(C[x][0]+1)*sizeof(int));
	C[x][C[x][0]]=c;
	
}
for(i=1;i<=n;i++) d[i]=oo;

//initializare

d[x0]=0;
for(i=1;i<=A[x0][0];i++)
	d[ A[x0][i] ] = C[ x0 ][ i  ];

x=x0; viz[x0]=1;

for(i=1;i<=n;i++)
{
	min=oo;
	for(j=1;j<=n;j++)
		if(!viz[j])
			if(min > d[j] )
				{min=d[j]; x=j;}
	viz[x]=1;
	for(j=1;j<=A[x][0];j++)
	{
		y=A[x][j];
		if( !viz[y] && d[y] > C[x][j] + min )
			d[y] = C[x][j] + d[x];	
	}

}

for(i=2;i<=n;i++)
	if(d[i]==oo)
		fprintf(g,"0 ");
	else fprintf(g,"%d ",d[i]);
fprintf(g,"\n");

fclose(f);
fclose(g);
return 0;
}