/*  Algoritmul lui Bellman Ford cu coada    */
#include <stdlib.h>
#include <stdio.h>
#define N 50010
#define INF 250000010
int *cine[N];        // cine[i][j] va fi cine este vecinul al j-lea al lui i
int *cost[N];        // cost[i][j] va fi costul muchiei de la i la cine[i][j]
int dist[N];         // aici in vector vor fi distantele la sfarsit
                     // atentie! trebuie inititalizat cu infinit pt a se reactualiza.
int n,m;             // n=numarul de varfuri, m=numarul de muchii
int cati[N];         // cati[i] este numarul veciniilor lui i
int incoada[N];      // incoada[i]=1 daca nodul i este in coada la momentul actual sau 0 in caz contrar
int coada[500000];   // coada in care tin nodurile pentru algoritmul bellman ford
void scan(){
    int i,j,c,aux,nr;
    char s[23];
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int v[5];
    gets(s);/*     citesc n si m       */
    aux=0;
    nr=0;
    for(i=0;s[i];++i)
        if(s[i]==' '){
            n=aux;
            aux=0;
        }
        else
            aux=aux*10+s[i]-'0';
    m=aux;
    while (m--){/*     citesc i,j,c  */
      gets(s);
      aux=0;nr=0;
      for (i=0;s[i];++i){
        if (s[i]==' '){
            v[++nr]=aux;
            aux=0;
        }
        else
            aux=aux*10+s[i]-'0';
      }
      i=v[1];
      j=v[2];
      c=aux;
      ++cati[i]; // modific numarul veciniilor lui i
      cine[i]=(int*)realloc(cine[i],cati[i]*sizeof(int)+4); // realoc lista de adiacenta
      cine[i][cati[i]]=j;
      cost[i]=(int*)realloc(cost[i],cati[i]*sizeof(int)+4); // realoc lista cu costuri
      cost[i][cati[i]]=c;
    }
}
void bellman_ford(){
    int p,u,i;
    int e,now;
    p=u=0;
    coada[u++]=1;
    for (i=1;i<=n;++i)// initializez cu INFINIT
       dist[i]=INF;
    dist[1]=0;
    while ((p^u)!=0){  //   cat timp coada nu este vida
      e=coada[p++];// scot nodul e din coada
      incoada[e]=0;// il marchez ca scos din coada
      for (i=1;i<=cati[e];++i){// parcurg toti vecinii lui e
         now=cine[e][i]; // now este vecinul urmator
         if(dist[now] > dist[e] + cost[e][i]){// daca se obtine o distanta mai buna
            dist[now] = dist[e] + cost[e][i];// modific distanta
            if (!incoada[now]){// daca nu este in coada
              incoada[now]=1;// il marchez ca fiind in coada
              coada[u++]=now;// il introduc in coada
            }
         }
      }
    }
}
void print(){
    int i,j;
    for (i=2;i<=n;++i){
        if (dist[i]==INF)
           dist[i]=0;
        printf("%d ",dist[i]);
    }
    fclose(stdin);
    fclose(stdout);
    exit(0);
}
int main(){
    scan();
    bellman_ford();
    print();
          }