#include<fstream>
const int inf=1<<30;
using namespace std;

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

int n,m;
int d[50001],h[50001],poz[50001];
int el_min;
int i,j,k,nr,sizeheap;

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

graf* b[50001];

void add(int x, int y, int z)
{graf* q = new graf;
 q->cost=z;
 q->nod=y;
 q->next=b[x];
 b[x]=q;
     }
     
void afisare()
{for(i=2; i<=n; i++)
 if(d[i]==inf)
  g<<"0 ";
 else 
 g<<d[i]<<" ";
}     
     
void swap_heap_elements(int x, int y)
{int aux=h[x];
 h[x]=h[y];
 h[y]=aux;}     
     
void sift(int x, int size) 
{int sohn;
 do{
   sohn=0;
   if((x<<1)<=size)
      {sohn=x<<1;
      if(sohn+1<=size && d[h[sohn+1]]<d[h[sohn]])
         sohn++;
      }     
   
  if(sohn && d[h[sohn]]<d[h[x]])
   {poz[h[sohn]]=x;
    poz[h[x]]=sohn;
    swap_heap_elements(sohn,x);
    x=sohn;}
  else
    sohn=0;  
  }while(sohn);
}
     
void percolate(int x, int size)
{int vater;
 do{vater=0;
 if((x>>1)>=1)
    vater=x>>1;
 if(vater && d[h[vater]]>d[h[x]])
   {poz[h[vater]]=x;
    poz[h[x]]=vater;
   swap_heap_elements(vater,x);
   x=vater;} 
 else
  vater=0;    
  }while(vater);
}         

int main()
{f>>n>>m;
int x,y,z;
for(i=1; i<=m; i++)
  {f>>x>>y>>z;
   add(x,y,z);}
   
for(i=1; i<=n; i++)
 {d[i]=inf; poz[i]=-1;}   
   
d[1]=0;

sizeheap=1;  h[1]=1;  poz[1]=1;
while(sizeheap)
{el_min=h[1];
 swap_heap_elements(1,sizeheap);
 sizeheap--;
 poz[h[1]]=1;
 sift(1,sizeheap);
 

 graf* q=b[el_min];
  while(q)
 {if(d[q->nod]>d[el_min]+q->cost)
   { d[q->nod]=d[el_min]+q->cost;
    if(poz[q->nod]==-1)
      {sizeheap++;
       h[sizeheap]=q->nod;
       poz[q->nod]=sizeheap;
       percolate(sizeheap,sizeheap);}
    else
      percolate(poz[q->nod],sizeheap);   
   }
  q=q->next;
}
//afisare();
//g<<endl;
}   

afisare();
f.close();
g.close();
return 0;}