#include <cstdio>    
  
#define FIN "dijkstra.in"   
#define FOUT "dijkstra.out"   
#define MAX_N 50005   
#define INF 0x3f3f3f3     
     
typedef struct NOD      
{      
    int nod, cost;      
    NOD *next;      
};      
     
int N, M, i, k;      
NOD *A[MAX_N];      
  
int D[MAX_N]; // distante   
int H[MAX_N]; // heap   
int P[MAX_N];      
     
    void readdata()      
    {      
         int x, y, c, i;   
       
         scanf("%d %d", &N, &M);      
         for (i = 1; i <= M; ++i)      
         {      
             scanf("%d %d %d", &x, &y, &c);      
             NOD *q = new (NOD);   
             q->nod = y, q->cost = c, q->next = A[x], A[x] = q;   
         }      
    }      
     
    void lift(int c)      
    {      
        int d;      
        while (c > 1)      
        {      
              d = c >> 1;  // fiul    
              if (D[ H[d] ] > D[ H[c] ])      
              {      
                  P[ H[c] ] = d, P[ H[d] ] = c;      
                     
                  // urcam in heap   
                  int ax = H[d]; H[d] = H[c], H[c] = ax;   
                     
                  // actualizam fiul   
                  c = d;      
              }      
              else c = 1;      
        }      
    }      
     
    void sink(int c)      
    {      
        int s; // fiu   
        while (c << 1 <= k)   
        {   
              s = c << 1;   
              if ((s|1) <= k && D[ H[(s|1)] ] < D[ H[s] ]) s |= 1;   
                 
              if (D[ H[s] ] < D[ H[c] ])   
              {   
                  P[ H[s] ] = c, P[ H[c] ] = s;   
                        
                  int ax = H[s]; H[s] = H[c], H[c] = ax;                  
                  c = s;   
              }   
              else return;   
        }            
    }      
     
    // k - nr de elemente din heap   
    void solve()      
    {       
         int i;   
         // initializari   
         for (i = 2; i <= N; ++i)      
             D[i] = INF, P[i] = -1;      
            
         P[1] = 1, H[++k] = 1;      
     
         while (k)      
         {      
                
             int min = H[1];      
             // scot elementul din heap   
             int ax = H[1]; H[1] = H[k]; H[k] = ax;      
             P[H[1]] = 1;      
             --k, sink(1);      
                
                
                
             for (NOD *q = A[min]; q != NULL; q = q->next)      
                 if (D[q->nod] > D[min] + q->cost)      
                 {      
                     D[q->nod] = D[min] + q->cost;      
     
                     if (P[q->nod] != -1) lift(P[q->nod]);      
                        
                        else H[++k] = q->nod, P[H[k]] = k, lift(k);         
                 }   
         }      
    }      
     
    int main()      
    {      
         freopen (FIN, "r", stdin);   
         freopen (FOUT, "w", stdout);   
       
         readdata();      
         solve();      
     
         for (i = 2; i <= N; ++i)      
             if (D[i] != INF) printf ("%d ", D[i]); else printf ("0 ");   
     
         return 0;      
    }