#include<fstream.h>
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
long viz[50010],n,m,d[50010];
struct coada
{
long inf;
coada *urm;
}*c,*ultim;

struct elem
{
long inf;
int cost;
elem *urm;
}*a[50010];
void citire()
{
int x,y,co;
elem *p;
f>>n>>m;
for(int i=0;i<m;i++)
	{
	f>>x>>y>>co;
	p=new elem;
	p->inf=y;
	p->cost=co;
	p->urm=a[x];
	a[x]=p;
	}

}
void prima()
{
elem *p;
d[1]=0;
for(int i=2;i<=n;i++)
{
	d[i]=2000000000;
}

}
void implementare()
{
 coada *q,*t;
 elem *p;
 c=new coada;
 c->inf=1;
 c->urm=NULL;
 viz[1]=1;
 ultim=c;
 while(c!=NULL)
 {

	p=a[c->inf];
	while(p!=NULL)
	{
	if(d[p->inf]>d[c->inf]+p->cost)
		{
		d[p->inf]=d[c->inf]+p->cost;
		if(viz[p->inf]==0)
			{
			q=new coada;
			viz[p->inf]=1;
			q->inf=p->inf;
			q->urm=NULL;
			ultim->urm=q;
			ultim=q;
			}
		}
	p=p->urm;
	}
 t=c;
 viz[c->inf]=0;
 c=c->urm;
 delete t;
 }

}
void afisare()
{
for(int i=2;i<=n;i++)
	{
	if(d[i]==2000000000)
		g<<0<<' ';
	else
		g<<d[i]<<' ';
	}
}
int main()
{
citire();
prima();
implementare();
afisare();
g.close();
return 0;
}