#include<stdio.h>

using namespace std;

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]=1001;
  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){
       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]==1001)  d[i]=0;
    fprintf(fout, "%d ", d[i]);
  }
  fprintf(fout, "\n");
  fclose(fout);
  return 0;
}