#include<stdio.h>
#define INF 50000011

struct nod {int inf;nod *urm;int c;} *v[50011];
int j,viz[50011],i,n,m,a,b,c,C[50011],min,pmin;

void djk () {

nod *p;

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

C[1]=0;

    for(i=1;i<=n;i++){
    //min
    min=INF;
    
      for(j=1;j<=n;j++){
        if(C[j] < min && !viz[j]){
        min=C[j];
        pmin=j;
        }
      }

      p=v[pmin];
      viz[pmin]=1;

      for(;p!=NULL;p=p->urm){

        if(C[p->inf] > (C[pmin] + p->c ) )
        C[p->inf]=C[pmin] + p->c;

      }

    }

}


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,&c);

   nod *p=new nod;
   p->inf=b;
   p->c=c;
   p->urm=v[a];
   v[a]=p;
  }

fclose(f);


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

djk();


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

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

  }

fclose(g);

return 0;
}