#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 coada[50005];//va tine indicii nodurilor
int li,ls;

int main(){
  int i,j,a,b,c;
  int n,m,poz,min;
  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
  d[0]=0;
  for(i=0;i<l[0];i++){
      d[lista[0][i].nod]=INF;//lista[0][i].cost;
  }
  li=0;ls=1;
  coada[li]=0;

  while(ls>li){
    for(j=0;j<l[li];j++){
        if(d[lista[li][j].nod]>d[li]+lista[li][j].cost){
          d[lista[li][j].nod]=d[li]+lista[li][j].cost;
          if(s[lista[li][j].nod]==0){
             coada[ls++]=lista[li][j].nod;  
             s[lista[li][j].nod]=1;
           }
        }
    }
 li++; 
 }
    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;    
}