# include <fstream.h>

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

struct nod 
{
	int info,cost;
	nod *urm;
}*p,*v,*q,*a[50005];



int d[50005],i,k,n,m,min,inf=32000000,x,y,z,nr,kk;
int main ()
{
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y>>z;
		p=new nod;
		p->info=y;
		p->cost=z;
		p->urm=a[x];
		a[x]=p;
	 if (x==1)
	 {	
		d[y]=z;
	    q=new nod;
		q->info=y;
		q->cost=z;
		q->urm=v;
		v=q;
	 }
	}
	for (i=1;i<=n;i++)
		if (d[i]==0)
			d[i]=inf;
	
	k=1;
	while (k<=n)
	{
		min=inf;
		p=v;
		kk=0;
		while (p)
		{ 
				if (min>d[p->info] && p->cost!=-1)
			{    
				min=d[p->info];
			    nr=p->info;
			}
				if (p->urm)
			if (d[p->urm->info]<min)
			{
			    q=p;
				kk=1;
			}
			
			p=p->urm;
		}
		if (kk==0)
			{if (v->urm)
		    	v=v->urm;
			}
			else
			if (q->urm)
			q->urm=q->urm->urm;
		p=a[nr];
		while (p)
		{
			if (d[p->info]==inf)
			{
				d[p->info]=d[nr]+p->cost;
			q=new nod;
				q->info=p->info;
				q->cost=p->cost;
			q->urm=v;
			v=q;
			}
			else
				if (d[p->info]>d[nr]+p->cost)
					d[p->info]=d[nr]+p->cost;
		p=p->urm;	
		}
		k++;
	}
	
	for (i=2;i<=n;i++)
		if (d[i]==inf)
			g<<"0 ";
		else
			g<<d[i]<<" ";
		f.close ();
		g.close ();
		return 0;
}