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

#define INF 2000000000
using namespace std;

struct NOD{
   int nod;
   int cost;
};


vector <NOD> lista[50005];
int d[50005],l[50005];
bool s[50005];
int coada[50005];//va tine indicii nodurilor
int li,ls;

int main(){
  int i,j,a,b,c;
  int n,m;
  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, care sunt la un mom dat in coada
  d[0]=0;
  li=0;ls=1;
  coada[li]=0;

  while(ls!=li){
    for(j=0;j<l[coada[li]];j++){
        if(d[lista[coada[li]][j].nod]>d[coada[li]]+lista[coada[li]][j].cost){
          d[lista[coada[li]][j].nod]=d[coada[li]]+lista[coada[li]][j].cost;
          if(s[lista[coada[li]][j].nod]==0){
             coada[ls++]=lista[coada[li]][j].nod;
             ls=ls%50000;
             s[lista[coada[li]][j].nod]=1;
           }
        }
    }
  li++;//am scos nodul coada[li] din coada..trebuie sa marchez asta
  s[coada[li-1]]=0;
  li=li%50000;
 }
    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;    
}