#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;   
    }