#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define Nmax 50013
#define inf 20*1000000
#define nod first
#define l64 long long
#define cost second
typedef struct celula {
                       int nod;
                       int cost;
                       celula* next;
                       }*lista;
lista G[Nmax];
int i,j,n,m,a,b,c,lheap(0),x,y;
l64 D[Nmax];
l64 Heap[Nmax];
int poz[Nmax];

void heap_down(int nod,int lheap)
 {
  int fiu=nod*2;
  if (fiu>lheap) return ;
  if (fiu<lheap && D[Heap[fiu]]>D[Heap[fiu+1]]) ++fiu;	   
  if (D[Heap[fiu]]<D[Heap[nod]]) 
	 {
	  swap(poz[Heap[fiu]],poz[Heap[nod]]);
	  swap(Heap[fiu],Heap[nod]);
	  heap_down(fiu,lheap);
	 }
 }

void heap_up(int nod)
{
 int father=nod/2;
 if (!father) return;
 if (D[Heap[nod]]<D[Heap[father]])
      {
       swap(poz[Heap[nod]],poz[Heap[father]]);
       swap(Heap[nod],Heap[father]);
       heap_up(father);
	  }
}

void add_heap(int value)
{  
 ++lheap;
 Heap[lheap]=value;
 poz[value]=lheap;
 heap_up(lheap);
}

void erase_top(int &lheap)
{
 swap(poz[Heap[1]],poz[Heap[lheap]]);
 swap(Heap[1],Heap[lheap]);
 --lheap;
 heap_down(1,lheap);
}

void dijkstra(int nod)
{
 for (int i=1;i<=n;++i) 
    {
	if (i==1) D[i]=0; 
	     else D[i]=inf;         
    add_heap(i);
    }
    
while(lheap>0)
   {
   	int virf=Heap[1];
   	erase_top(lheap);
   	lista r=G[virf];
   	while(r)
   	   {
   	   	if (D[r->nod]>D[virf]+r->cost)
   	   	     {
   	   	      D[r->nod]=D[virf]+r->cost;
   	   	      heap_up(poz[r->nod]);
			 } 
	   r=r->next;	
	   }
   }	
}

void add(int nod,int cost,lista &p)
{
  lista r=new celula;
  r->nod=nod;
  r->cost=cost;
  r->next=p;
  p=r;
}  

int main(void)
{
 ifstream in("dijkstra.in");
 ofstream out("dijkstra.out");
 in>>n>>m;
 while(m--)
  {
   in>>a>>b>>c;
   add(b,c,G[a]);
  }
dijkstra(1);
for (i=2;i<=n;++i) out<<D[i]<<" ";
return 0;
}