#include <stdio.h>

#define MAXn 50001
#define inf 1 << 30
#define undef -1

 struct graf 
       {
	       int nod, dist;
	       graf *next;
       };


      int n, m, k, h [MAXn], poz [MAXn], d [MAXn];
      graf *f [MAXn];


void insert (int a, int b, int c)
	   {
		   graf *aux;
		   aux=new graf;
		   aux->nod=b;
		   aux->dist=c;
		   aux->next=f [a];
		   f [a]=aux;
	   }

void scan ()
         {
		 int i, a, b, c;
		 scanf ("%d %d", &n, &m);
		 for (i=1; i<=m; ++i)
		    {
			    scanf ("%d %d %d", &a, &b, &c);
			    insert (a, b, c);
		    }    

	 }	 

void init ()
	 {
		 int i;
		 for (i=2; i<=n; ++i)
		    {
			    d [i]=inf;
			    poz [i]=undef;
		    }	    
		 poz [1]=1;
		 h [1]=1;
		 k=1;
	 }

void swap (int a, int b, int v [])
	 {
		 int aux;
		 aux=v [a];
		 v [a]=v [b];
		 v [b]=aux;
	 }

void upheap (int t)
	   {
		   int p;
		   while (t != 1)
		        {
				p=k >> 1;
				if (d [h [t]] < d [h [p]])
			          {
					  swap (t, p, h);
					  swap (h [t], h [p], poz);
					  t=p;
				  }	
		               else   
				       t=1;		       
		        }   
	   }

void downheap (int t)
	     {
		     int f;
		     while (t <= k)
			  {
				  f=t;
				  if ((t << 1) <= k)
				    {
					  f=t << 1;
					  if ((f | 1) <=k && d [h [f]] > d [h [(f | 1)]])
				            {
						    f |= 1;
					    }		   
					 if (d [h [t]] > d [h [f]]) 
				           {
						   swap (t, f, h);
						   swap (h [t], h [f], poz);
						   t=f;
					   }	
			                else
			                        t=k+1;			
			            } 
		                  else		
					 t=k+1;  
			          	  
			  }	  
	     }

void dijkstra ()
	     {
		     graf *w;
		     init ();
		     while (k)
			  {
				  w=f [h [1]];
				  while (w)
				       {
					       if (d [w->nod] > w->dist + d [h [1]])
					         {
							 d [w->nod]=w->dist+d [h [1]];
							 if (poz [w->nod] == undef)
						           {
								   h [++k]=w->nod;
								   poz [w->nod]=k;
							   }
				                         upheap (poz [w->nod]);				
					         }      
					       w=w->next;
				       }       
                                swap (1, k, h);
                                poz [h [1]]=1;
                                --k;
				downheap (1);
			  }	  
	     }

void print ()
	  {
		  int i;
		  for (i=2; i<=n; ++i)
		       if (d [i] == inf)
		           printf ("0 ");
                       else
	                      printf ("%d ", d [i]);		       
	  }

int main ()
	 {
		 freopen ("dijkstra.in", "r", stdin);
		 freopen ("dijkstra.out", "w", stdout);
		 scan ();
		 dijkstra ();
		 print ();
		 return 0;
	 }