#include <vector>
#include <cstdio>

using namespace std;

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

struct nod{
  int nod,cost;
};

vector <nod> lista[MAXN];
int dist[MAXN];
int arbint[4*MAXN];
//int indice[MAXN];
int poz;


char buffer[BUF];
int pozitie=BUF-1;

void citeste(int &nr){
   while(buffer[pozitie]<'0' || buffer[pozitie]>'9'){//nu e cifra
         pozitie++;
         if(pozitie==BUF){
           fread(buffer,1,BUF,stdin);
           pozitie=0;
         }
  }
   nr=0;
   while(buffer[pozitie]>='0' && buffer[pozitie]<='9'){
        nr=nr*10+buffer[pozitie]-'0';
        pozitie++;
         if(pozitie==BUF){
           fread(buffer,1,BUF,stdin);
           pozitie=0;
         }
}
}

int val;

void react(int nod,int li, int ls){
      if(li==ls){
        arbint[nod]=val;
        return;
      }
      int mij=li+(ls-li)/2;
      //o iau prin stanga
      if(poz<=mij)react(nod*2,li,mij);
        else react(nod*2+1,mij+1,ls);//prin dreapta
      //reactualizez tot ce e mai sus de locul unde am introdu noua valoare
      //e minimul dintre cele doua intervale
      if(dist[arbint[nod*2]]<dist[arbint[nod*2+1]])arbint[nod]=arbint[nod*2];
        else arbint[nod]=arbint[nod*2+1];
}

int main(){
  freopen("dijkstra.in","r",stdin);
  freopen("dijkstra.out","w",stdout);
  int N,M,a,b,c;

  citeste(N);
  citeste(M);
 
  int i;
  nod aux;
  for(i=0;i<M;i++){
     citeste(a);
     citeste(b);
     citeste(c);
     aux.nod=b;
     aux.cost=c;
     lista[a].push_back(aux);
  }
  //final citire
  dist[0]=INF;
  //initializari
    for(i=2;i<=N;i++){
      dist[i]=INF; 
    }

    dist[1]=0;
    val=1;
    poz=1;
    //printf(":D\n");
    react(1,1,N);
    //printf(":D ind=%d min=%d\n",arbint[1],dist[arbint[1]]);
    //return 0;
    int k=N-1;
    int min,ind;
    int aux1,aux2;
    while(k){//cat timp mai sunt noduri neviz
       /*min=INF;
       for(i=2;i<=N;i++){       //alege dintre cele nevizitate
           if(poz[i]==0){
              //pe cel mai apropiat de sursa (cu dist minim)
              if(dist[i]<min){min=dist[i];ind=i;}
           }
       }*/
       ind=arbint[1];//atunci cand scot un nod, defapt ii dau un cost f mare, care sa nu afecteze minimul
       val=0;//pt ca dist[0]=INF;
       poz=ind;
       react(1,1,N);
       k--;
       //printf("ind=%d min=%d\n",ind,dist[ind]);
       //viz[ind]=1;
       //din acest nod incerc sa imbunatatesc ce am deja
       for(i=0;i<lista[ind].size();i++){
           //daca valoarea nodului lista[min][i] se poate imbunatati prin nodul min
           aux1=lista[ind][i].nod;
           aux2=dist[ind]+lista[ind][i].cost;
           if(dist[aux1]>aux2){
              dist[aux1]=aux2;
              //printf("dist[%d]=%d\n",aux1,aux2);
              val=aux1;
              poz=aux1;
              react(1,1,N);
           }
       } 
   }




    for(i=2;i<=N;i++){
       printf("%d ",(dist[i]==INF?0:dist[i]));
    }
  printf("\n");

return 0;
}