#include <stdio.h>
#define MAX 32768000

int costuri[20000][20000];
int d[20000],s[20000];
//int t[100];

/*void drum(int i){
  if(t[i])drum(t[i]);
  printf("%d ",i+1);
}*/

int main(){
  int i,j,a,b;
  int n,m,poz,min,nr;
  int r=0;//r este indicele nodului de pornire
  
  FILE *fin=fopen("dijkstra.in","r");
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      costuri[i][j]=MAX;

  for(i=0;i<m;i++){
       fscanf(fin,"%d%d",&a,&b);
       fscanf(fin,"%d",&costuri[a-1][b-1]);
  //t[i]=-1;
  }
  s[r]=1;//multimea nodurilor selectate
  nr=n-1;
  
  for(i=0;i<n;i++){
     d[i]=costuri[r][i];
  //   if(i!=r)
 //      if(d[i]<MAX)t[i]=r;
  }
  
  //for(i=0;i<n;i++)
  while(nr){
    min=MAX;
    for(j=0;j<n;j++){
       if(s[j]==0){
          //daca nu am mai considerat nodul j
          if(d[j]<min){
             min=d[j];
             poz=j;
          }
       }
    }
    s[poz]=1;
    nr--;
    for(j=0;j<n;j++){
      if(s[j]==0)
        if(d[j]>d[poz]+costuri[poz][j]){
          d[j]=d[poz]+costuri[poz][j];
  //        t[j]=poz;
        }
    }
    }
    /*for(i=0;i<n;i++){
      printf("%d ",d[i]);
    }*/
    //printf("\n");
    FILE *fout=fopen("dijkstra.out","w");
    for(i=1;i<n;i++){
      //if(i!=r){
         //if(t[i]!=-1){
            fprintf(fout,"%d ",d[i]);
            //printf("distanta minima de la %d la %i este %d\n",r+1,i+1,d[i]);
            //drum(i);
            //printf("\n");
         //}else{
           //printf("nu exista drum de la nodul %d la nodul %d\n",r+1,i+1);
           //fprintf(fout,"0 ");
        // }
      //}
    }
    fprintf(fout,"\n");
  
  
return 0;    
}