//////// program alg dijskta  /// alg costuri minime in graf orientate-neorientate
/*
  Name: bysorynyos
  Copyright: me
  Author: me
  Date: 04/02/08 11:51
  Description: up 
*/
//04/02/08 11:51

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <string.h>

#define IN "dijkstra.in"
#define OUT "dijkstra.out"

ifstream fin(IN);
ofstream fout(OUT);

#define maxn 50005
#define inf 0x3f3f

struct lista
{
 int nod;
 int c;
 
 lista *urm;
}*g[250005];

int n,m,s,d[maxn],t[maxn],h[maxn],poz[maxn],nh;
char u[maxn];

void adauga(int x,int y,int z);

void swap(int i,int j)
{
 int t;
     
 t=h[i];
 h[i]=h[j];
 h[j]=t;
 
 poz[h[i]]=i;
 poz[h[j]]=j;
}

void heapdw(int r,int k)
{
 int st,dr,i;
 
 if(2*r+1<=k)
 {
  st=h[2*r+1];
  
  if(2*r+2<=k)
   dr=h[2*r+2];
  else
   dr=st-1;
   
  if(st>dr)
   i=2*r+1;
  else
   i=2*r+2;
   
  if(d[h[r]]>d[h[i]])
  {
   swap(r,i);
   heapdw(i,k);
  }
 }
}                                           
           
void heapup(int k)
{
 int t;
 
 if(k<0)
  return ;
 
 t=(k-1)/2;
 
 if(d[h[k]]<d[h[t]])
 {
  swap(k,t);
  heapup(t); 
 }     
}

void buildh(int k)
{
 int i;
 for(i=1;i<k;i++)
  heapup(i);
}

int scoate_heap()
{
 swap(0,nh-1);
 poz[h[nh-1]]=0;
 nh--;
 heapdw(0,nh-1);
 return h[nh];
}

void dijkstra(int sursa)
{
 int i,nod;
 lista *p;
 
 memset(u,0,sizeof(u));
 memset(t,0,sizeof(t));
 memset(d,0x3f,sizeof(d));
 
 for(i=0;i<n;i++)
 {
  h[i]=i+1;
  poz[i+1]=i;           
 }
 
 d[sursa]=0;
 buildh(n);
 nh=n;
 
 while(nh>0)
 {
  nod=scoate_heap();
  
  for(p=g[nod];p;p=p->urm)
   if(d[p->nod]>d[nod]+p->c)
   {
    d[p->nod]=d[nod]+p->c;
    t[p->nod]=nod;
    heapup(poz[p->nod]);
   }
 }
}                                     

void citire();
void afis();


int main()
{
 citire();
 // fin.close();
  
 dijkstra(1);
 
 afis();
  fout.close();
  
return 0;
}      

void citire()
{
 int i;
 int x,y,cs;
 
 
 fin>>n>>m;

 for(i=1;i<=m;i++)
 {
  fin>>x>>y>>cs;
  adauga(x,y,cs);
  adauga(y,x,cs);
 }

}

void adauga(int x,int y,int z)
{
 lista *p;

 p=new lista;
 p->nod=y;
 p->c=z;
 p->urm=g[x];
 g[x]=p;
}

void afis()
{
 int i;

 for(i=2;i<=n;i++)
  fout<<d[i]<<" ";
}