#include<stdio.h>
#define INF 1<<30

struct nod{int inf,cost; nod *urm;} *v[50111];

int i,k,poz[50111],aux,n,m,a,b,cost,h[50111],C[50111],c;

void upheap(int x){
int c=x;
int t;
t=x>>1;

   while(t && C[h[c]] < C[h[t]]){

   poz[h[c]]=t;
   poz[h[t]]=c;

   aux=h[t];
   h[t]=h[c];
   h[c]=aux;

   c=t;
   t=c>>1;
   }

}


void downheap(int x){
int t=x;
int c=x<<1;

  if(c<k && C[h[c]] > C[h[c+1]] )
  c++;

    while(c<=k && C[h[t]] > C[h[t]]){

    poz[h[c]]=t;
    poz[h[t]]=c;

    aux=h[t];
    h[t]=h[c];
    h[c]=aux;

    t=c;
    x=t<<1;

      if(c<k && C[h[c]] > C[h[c+1]] )
      c++;
      
    }

}


void dijkstra(){

  for(i=2;i<=n;i++)
  C[i]=INF;

k++;
h[k]=1;
nod *q;

  while(k){
  int min=h[1];
  h[1]=h[k];
  poz[ h[1] ]=1;
  k--;
  downheap(1);

    for(q=v[min];q!=NULL;q=q->urm){

       if(C[q->inf] > C[min] + q->cost){

          if(poz[q->inf]==0){
          //il adaug in heap
          k++;
          C[q->inf] = C[min] + q->cost;
          poz[q->inf]=k;
          h[k]=q->inf;
          upheap(k);
          }

          else{
          //mai e in heap
          C[q->inf]=C[min] + q->cost;
          upheap(poz[q->inf]);
          }

       }

    }

  }


}



int main(){

FILE *f=fopen("dijkstra.in","r");
fscanf(f,"%d %d",&n,&m);

  for(i=1;i<=m;i++){
  fscanf(f,"%d %d %d",&a,&b,&cost);
     nod *p=new nod;
     p->inf=b;
     p->cost=cost;
     p->urm=v[a];
     v[a]=p;
  }

fclose(f);

dijkstra();
 
FILE *g=fopen("dijkstra.out","w");

 for(i=2;i<=n;i++)
   if(C[i]!=INF)
   fprintf(g,"%d ",C[i]);
   else
   fprintf(g,"%d ",0);
   
   
fclose(g);

return 0;
}