#include<stdio.h>
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

#define M 50010
#define oo 1010
long n,m;
int d[M];
bool viz[M];
typedef struct
{
	int x,y,c;
} VF;
VF v[M*5];

void cit()
{
	long i;
	fscanf(f,"%ld%ld",&n,&m);
	for(i=1;i<=m;++i)
		fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
	fclose(f);
}

void init()
{
	for(long i=2;i<=n;++i)
		d[i]=oo;
}

long min()
{
	long dmin=oo,q;
	for(long i=1;i<=n;++i)
		if(dmin>d[i] && viz[i]==0) {dmin=d[i]; q=i;}
	return q;
}

void react(long x)
{
	long i;
	for(i=1;i<=m;++i)
		if(v[i].x==x) if(d[v[i].y]>d[x]+v[i].c) d[v[i].y]=d[x]+v[i].c;
}

void djk()
{
	long i,vmin;
	
	for(i=1;i<=n;++i)
	{
		vmin=min();
		viz[vmin]=1;
		react(vmin);
	}
}

void afis()
{
	for(long i=2;i<=n;++i)
		fprintf(g,"%d ",d[i]);
	fclose(g);
}

int main()
{
	cit();
	init();
	djk();
	afis();
	return 0;
}