# include <fstream.h>

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

   void adauga (int x)
   {
	   sf++;
	   v[sf]=x;
	   int k=sf,aux;
	   while (k/2)
	   {
		   
		   if (d[v[k/2]]>d[v[k]])
		   {
			   aux=v[k/2];
			   v[k/2]=v[k];
			   v[k]=aux;
		   
           k=k/2;
	       }
		   else
			   k=0;
		}
		   
   }	   

   void mm (int k)
   {
	   while (v[k/2]>v[k] && k/2!=0)
	   {
		   aux=v[k];
		   v[k]=v[k/2];
		   v[k/2]=aux;
	   }
   }
   
   
   void cauta (int q)
   { 
	   if (v[q]==nrr)
	   {

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

    void stergmin ()
	{ 
		int k=1,ok=0,min=0;
		while (ok==0)
		{
			if (2*k+1<=sf)
			if (d[v[2*k]]<d[v[2*k+1]])
				min=2*k;
			else
				min=2*k+1;
			
			else
				if (2*k==sf)
					min=2*k;
				else
					ok=1;
		    if (ok==0)
			if (d[v[min]]<d[v[k]])
			{
				aux=v[min];
				v[min]=v[k];
				v[k]=aux;
			}
			else
				ok=1;
		}
	}
	

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;
	    adauga (y);
	 }
	}
	for (i=1;i<=n;i++)
		if (d[i]==0)
			d[i]=inf;
	
	k=1;
	while (k<=n)
	{
		
		
		nr=v[1];
		v[1]=v[sf];
		sf--;
		stergmin ();
		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);
				}
		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;
}