#include<stdio.h>
#define MAX 50001
int n,m,d[MAX],s[MAX],p[MAX],X,L[3][300002],cont;
void init()
{
	int i;
	for(i=1;i<=n;++i)
		d[i] = 999999;
	cont = n+1;
	X = 1;
	s[X] = 1;
}
void add(int x,int y,int c)
{
	if(!L[1][x])
	{
		L[1][x] = cont;
	}
	else
	{
		L[1][L[0][x]] = cont;
	}
	L[0][x] = cont;
	L[0][cont] = y;
	L[2][cont] = c;
	++cont;
}
int detmin()
{
	int i,min = 999999,p = 0;
	for(i=1;i<=n;++i)
		if(d[i]<min && !s[i]){p = i;min = d[i];}
	return p;
}
void make(int min)
{
	int var = L[1][min],j;
	while(var)
	{
		j = L[0][var];
		if(L[2][var] + d[min] < d[j])
		{
			d[j] = L[2][var] + d[min];
			p[j] = min;
		}
		var = L[1][var];
	}
}
int main()
{
	FILE*f = fopen("dijkstra.in","r");
	fscanf(f,"%d %d",&n,&m);
	init();
	int x,y,c,i;
	for(i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&x,&y,&c);
		if(x == X)
		{
			d[y] = c;
			p[y] = x;
		}
		else add(x,y,c);
	}
	fclose(f);
	d[X] = 0;
	
	int nr = 1;
	while(nr<=n)
	{
		i = detmin();
		s[i] = 1;
		
		make(i);		
		++nr;
	}
	
	FILE*g = fopen("dijkstra.out","w");
	for(i=2;i<=n;++i)
	{
		if(d[i] == 999999){fprintf(g,"0 ");continue;}
		fprintf(g,"%d ",d[i]);
	}
	fclose(g);
	return 0;
}