#include <fstream.h>

struct nod{
	long inf,co;
	nod *urm;}*l[50001];
	
long n,m,r,j,c,min,i,d[50001],s[50001],k;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void add(long x,long y,long c)
{
	nod *q=new nod;
	q->inf=y;
	q->co=c;
	q->urm=l[x];
	l[x]=q;
}

long exista(long x,long y)
{
	nod *p=l[x];
	while(p)
	{
		if(p->inf==y)
			return p->co;
		p=p->urm;
	}
	return 50000;
}	
			

void cit()
{
	int i,x,y,c;
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		add(x,y,c);
	}
	fin.close();
}

int main()
{
	cit();
	r=1;
	for(i=1;i<=n;i++)
	{
		d[i]=exista(r,i);
			s[i]=0;
	}
	s[r]=1;
	d[r]=0;
	for(k=1;k<n;k++)
	{
		min=50000;
		for(i=1;i<=n;i++)
			if(!s[i]&&d[i]<min)
			{
				min=d[i];
				j=i;
			}
		/*for(i=1;i<=n;i++)
			if(!s[i]&&d[i]>d[j]+exista(j,i))
				d[i]=d[j]+exista(j,i);*/
		nod *t = l[j]; 
		while ( t ) 
		{	    
			if ( d[ t->inf ] > d[j] + t->co )                 
				d[ t->inf ] = d[j] + t->co; 
			t = t->urm; 
       
} 

		s[j]=1;
}
	for(i=2;i<=n;i++)
		fout<<d[i]<<" ";
				
	fout.close();
	return 0;
}