#include<iostream.h>
#include<fstream.h>
using namespace std;
struct nod{ int inf;
			int cost;
			nod *leg;
}*l[50000];
//int d[100000];
/*void bf(int nodul)
{
	nod *p;
	int ic,sfc,s[100000],c[100000];
	ic=sfc=0;
	s[nodul]=1;
	c[ic]=nodul;
	d[nodul]=0;
	while(ic<=sfc)
	{
		for(p=l[c[ic]];p!=NULL;p=p->leg)
			if(!s[p->inf])
			{
			s[p->inf]=1;
			sfc++;
			c[sfc]=p->inf;
			d[p->inf]=d[c[ic]]+1;
		}
	ic++;
	}
}*/
int main()
{
	int min,n,m,s[50000],x,y,poz,k,i,d[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]<<" ";
	return 0;
}