# include <fstream.h>

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
int d[500005],i,k,n,m,nrr,min,inf=32000000,x,y,z,nr,sf,v[500005],aux,ok;
struct nod 
{
	int info,cost;
	nod *urm;
}*p,*q,*a[500005];

void sss (int k)
 {
	 if (k/2)
		 if (d[v[k/2]]>d[v[k]])
		 {
			 aux=v[k];
			 v[k]=v[k/2];
			 v[k/2]=aux;
			 sss (k/2);
		 }
}

void jjj (int k)
{
	if (2*k+1<=sf)
	{
		if (d[v[2*k]]<d[v[2*k+1]])
			min=2*k;
		else
			min=2*k+1;
		if (d[v[min]]<d[v[k]])
		{
			aux=v[min];
			v[min]=v[k];
			v[k]=aux;
			jjj (min);
		}
	}
	else
		if (2*k<=sf)
			if (d[v[2*k]]<d[v[k]])
			{
				aux=v[k];
				v[k]=v[2*k];
				v[2*k]=aux;
			}
}




void adauga (int x)
   {
	   sf++;
	   v[sf]=x;
	   sss (sf);
   }	   

  
	
	

    void mm (int k)
	{ int ok=0;
		if (k/2)
			
				if (d[v[k/2]]>d[v[k]])
				{
					sss (k);
			    	ok=1;
				}
		if (ok==0)
			jjj (k);
	}

	void sterg (int k)
	{
		v[k]=v[sf];
		sf--;
		mm (k);
	}

	void cauta (int q)
{
	if (v[q]==nrr)
	sterg (q);
	else
	{
		if (2*q+1<=sf)
			if (d[v[2*q+1]]<=nrr)
			cauta (2*q+1);
		if (2*q<=sf)
			if (d[v[2*q]]<=nrr)
				cauta (2*q);
	}
}
	
   




int main ()
{
	f>>n>>m;
	for (i=1;i<=n;i++)
		d[i]=-1;
	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;
	    adauga (y);
	 }
	}
	for (i=1;i<=n;i++)
		if (d[i]==-1)
			d[i]=inf;
	
	k=1;
	while (k<=n)
	{
		
		
		nr=v[1];
		v[1]=v[sf];
		
		sterg (1);
		p=a[nr];
		
		while (p)
		{
			if (d[p->info]==inf)
			{
				d[p->info]=d[nr]+p->cost;
		     adauga (p->info);
			}
			else
				if (d[p->info]>d[nr]+p->cost)
				{
					nrr=p->info;
					d[p->info]=d[nr]+p->cost;
					cauta (1);
					adauga (p->info);
				}
		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;
}