#include <stdio.h>
#include <vector>

#define INF 2000000000
using namespace std;

struct NOD{
   int nod;
   int cost;
};


vector <NOD> lista[50005];
int d[50005],s[50005],l[50005];

int main(){
  int i,j,a,b,c;
  int n,m,poz,min,nr;
  NOD aux;
  FILE *fin=fopen("dijkstra.in","r");
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;i<n;i++)
     d[i]=INF;

  for(i=0;i<m;i++){
      fscanf(fin,"%d%d%d",&a,&b,&c);
      aux.nod=b-1;
      aux.cost=c;
      lista[a-1].push_back(aux);
      l[a-1]++;
   }

  s[0]=1;//multimea nodurilor selectate
  nr=n-1;
  d[0]=0;
  for(i=0;i<l[0];i++){
      d[lista[0][i].nod]=lista[0][i].cost;
  }
  
  while(nr){
    min=INF;
    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<l[poz];j++){
      if(s[lista[poz][j].nod]==0)
        if(d[lista[poz][j].nod]>d[poz]+lista[poz][j].cost){
          d[lista[poz][j].nod]=d[poz]+lista[poz][j].cost;
        }
    }
    }
    FILE *fout=fopen("dijkstra.out","w");
    for(i=1;i<n;i++){
            fprintf(fout,"%d ",(d[i]==INF?0:d[i]));
    }
    fprintf(fout,"\n");
  
  
return 0;    
}