#include<iostream.h>
#include<fstream.h>
using namespace std;
struct nod{ int inf;
			int cost;
			nod *leg;
}*l[50000];
int main()
{
	int min,n,m,s[50000],x,y,poz,k,i,d[50000],t[50000];
	nod *p;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
	 f>>x>>y>>k;
		p=new nod;
		p->inf=y;
		p->cost=k;
		p->leg=l[x];
		l[x]=p;
    }
	for(i=1;i<=n;i++)
	{
	d[i]=64000;
	s[i]=0;
    }
	s[1]=1;
	for(p=l[1];p!=NULL;p=p->leg)
		{
			d[p->inf]=p->cost;
			if(p->inf!=1)
				if(d[p->inf]<64000) 
				t[p->inf]=1;
	}
	for(i=1;i<=n-1;i++)
	{
		min=64000;
		for(p=l[1];p!=NULL;p=p->leg)
		if(s[p->inf]==0)
		  if(d[p->inf]<min)
		  {
			min=d[p->inf];
		    poz=p->inf;
		  }
		s[poz]=1;
		for(p=l[poz];p!=NULL;p=p->leg)
		 if(s[p->inf]==0)
			if(d[p->inf]>d[poz]+p->cost)
			{
				d[p->inf]=d[poz]+p->cost;
			    t[p->inf]=poz;
			}
	}
	//bf(s);
	for(i=2;i<=n;i++)
	g<<d[i]<<" ";
	drum(i);
	return 0;
}