#include <vector>
#include <cstdio>

using namespace std;

#define MAXN 50005
const int INF=1<<30;

struct nod{
  int nod,cost;
};

vector <nod> lista[MAXN];
int dist[MAXN];
int heap[MAXN],k;//k este nr de noduri din heap
int poz[MAXN];//0 daca nu e in heap , indicele locului in heap daca este deja in heap

void urca(int loc){
   int x;
   int aux;
   while(loc>1){
      x=loc>>1;
      if(dist[heap[loc]]<dist[heap[x]]){
        //interschimb nodul de pe locul loc cu tatal sau
        poz[heap[x]]=loc;
        poz[heap[loc]]=x;
        aux=heap[loc];
        heap[loc]=heap[x];
        heap[x]=aux;
        loc=x;
      }else loc=1;
   }
}

void coboara(int loc){
   //cobor in fiul cel mai mic dintre cei doi
int fiu,aux;
    while ( loc <= k ){
      fiu = loc;
      //incerc fiul din stanga
      if ( (loc<<1) <= k ){
         fiu = loc << 1;
         if ( (fiu + 1) <= k )
              if ( dist[heap[fiu+ 1]] < dist[heap[fiu] ] )
                  fiu++;
      }else return;
      if (dist[heap[loc]] > dist[heap[fiu]]){
            poz[heap[loc]]= fiu;
            poz[heap[fiu]] = loc;
            aux=heap[loc];
            heap[loc]=heap[fiu];
            heap[fiu]=aux;
            loc=fiu;
        }
        else
            return;
    }


}

int main(){
  FILE *fin=fopen("dijkstra.in","r");
  FILE *fout=fopen("dijkstra.out","w");
  int N,M,a,b,c;
  fscanf(fin,"%d%d",&N,&M);
  int i;
  nod aux;
  for(i=0;i<M;i++){
     fscanf(fin,"%d%d%d",&a,&b,&c);
     aux.nod=b;
     aux.cost=c;
     lista[a].push_back(aux);
  }
  //final citire
  //initializari
    for(i=2;i<=N;i++){
      dist[i]=INF;
      //poz[i]=-1;//nu sunt in heap
    
    }
    dist[1]=0;
    poz[1]=1;
  k=1;//cate noduri sunt in heap
    //adaug sursa in heap
    heap[1]=1;
  int min,aux1,aux2;
    while(k){//cat timp heapul nu e vid
       min=heap[1];//e min-heap; tine doar noduri nevizitate in el
      //scot varful heapului....
       heap[1]=heap[k];
       poz[heap[1]]=1;
       k--;
       coboara(1);
       //heap tine indicii nodurilor 
       for(i=0;i<lista[min].size();i++){
           //daca valoarea nodului lista[min][i] se poate imbunatati prin nodul min
           aux1=lista[min][i].nod;
           aux2=lista[min][i].cost;
           if(dist[aux1]>dist[min]+aux2){
                 dist[aux1]=dist[min]+aux2;
                 //am imbunatatit val nodului lista[min][i]
                 if(poz[aux1]){
                    //e deja in heap, doar ca acum are alta valoare, mai mica
                    //trebuie urcat in heap
                    urca(poz[aux1]);
                 }else{
                    //nu e in heap, trebuie adaugat
                    heap[++k]=aux1;
                    poz[heap[k]]=k;
                    urca(k);
                 }
           }
       }
    }
    for(i=2;i<=N;i++){
       fprintf(fout,"%d ",(dist[i]==INF?0:dist[i]));
    }
  fprintf(fout,"\n");

return 0;
}