#include<stdio.h>

const int infi=250000099;
struct nod{
  int info;
  int cost;
  nod* urm;
} *v[500001];

int d[500001], q[500001], poz[500001];

int n, m, hsize;

FILE *fin,*fout;

void initus(){
  int i;
  for(i=1;i<=n;i++)
    d[i]=infi;
  d[1]=0;
}

void intersch(int &a, int &b){
  int aux=a;
  a=b;   
  b=aux;   
}   
  
void heapify(int i){   
  int min=i;   
  if((i<<1)<=hsize) if( d [ q[min] ] > d [ q [ (i<<1) ] ] )       min=(i<<1);   
  if((i<<1)+1<=hsize) if( d [ q[min] ] > d [ q [ (i<<1)+1 ] ] )       min=(i<<1)+1;   
  poz[q[min]]=i;   
  poz[q[i]]=min;   
  intersch( q[min], q[i] );   
  if( min!=i ) heapify( min );   
}   
void update(int i){   
  int j=poz[i];   
  while(j>1 && d[q[j/2]]>d[q[j]]){   
       poz[q[j/2]]=j;   
       poz[q[j]]=j/2;;   
       intersch(q[j/2],q[j]);   
       j=j/2;   
  }   
}   
  
void buildheap(){   
  int i;   
  for(i=1;i<=n;i++){   
    q[i]=i;   
    poz[i]=i;   
  }   
  hsize=n;   
  for(i=n/2;i>0;i--)   
    heapify(i) ;   
}   
  
int extrmin(){   
   int mi=q[1];   
   poz[q[1]]=hsize;   
   poz[q[hsize]]=1;   
   intersch(q[1], q[hsize]);   
   hsize--;   
   heapify(1);   
   return mi;   
}   
void relax(int n1, int n2, int c){   
   if(d[n2]>d[n1]+c)   
     d[n2]=d[n1]+c;   
}   
void dijkstra(){   
  initus();   
  buildheap();   
  int u;   
  nod*p;   
  while(hsize){   
     u=extrmin();
     p=v[u];   
     while(p){   
       if(poz[p->info]<=hsize){
	 relax(u, p->info, p->cost );
	 update(p->info);
       }
       p=p->urm;   
     }   
  }   
}   
  
void add(nod *&vf, int x, int y){   
  nod* p=new nod;   
  p->info=x;   
  p->cost=y;   
  p->urm=vf;   
  vf=p;   
}   
  
int main(){   
  int i, x, y, z;   
  fin=fopen("dijkstra.in", "rt");   
  fscanf(fin, "%d%d", &n, &m);   
  for(i=0;i<m;i++){   
    fscanf(fin, "%d%d%d", &x, &y, &z);   
    add(v[x],y,z);   
  }   
  fclose(fin);   
  dijkstra();   
  fout=fopen("dijkstra.out", "wt");   
  for(i=2;i<=n;i++){
    if(d[i]==infi)  d[i]=0;   
    fprintf(fout, "%d ", d[i]);   
  }   
  fprintf(fout, "\n");   
  fclose(fout);   
  return 0;   
}