#include <cstdio>   
#include <cstring>

using namespace std;

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define MAX_N 100005
#define INF 0x3f3f3f3f

int N, M, K;

int D[MAX_N];
int H[MAX_N];
int P[MAX_N];

typedef struct NOD
{
        int nod;
        int cost;
        NOD *next;
};

NOD *A[MAX_N];

    void readdata ()
    {
         scanf ("%d %d", &N, &M);
         
         int x, y, c, i;
         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 sink (int c)
    {
         int s;
         while (c << 1 <= K)
         {
               s = c << 1;
               if ((s|1) <= K && H[(s|1)] < H[s]) s |= 1;
               
               if (D[ H[c] ] > D[ H[s] ])
               {
                      P[ H[c] ] = s, P[ H[s] ] = c;
                      
                      int ax = H[c]; H[c] = H[s], H[s] = ax;
                      c = s;
               } 
               else return;
         }
    }
    
    void lift (int c)
    {
         int d;
         while (c > 1)
         {
               d = c >> 1;
               if (D[ H[c] ] < D[ H[d] ])
               {
                      P[ H[d] ] = c, P[ H[c] ] = d;
                      
                      int ax = H[c]; H[c] = H[d], H[d] = ax;
                      c = d;
               }
               else return;
         }
    }
    
    void solve ()
    {
         int i;
         
         for (i = 1; i <= N; ++i) D[i] = INF, P[i] = -1;
         D[1] = 0, H[++K] = 1, P[1] = 1;
         
         while (K)
         {
               int min = H[1];
               H[1] = H[K--];
               P[ H[1] ] = 1;
               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) H[++K] = q->nod, P[q->nod] = K, lift (K);
                      else lift (P[q->nod]);
               }
         }      
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        readdata ();
        solve ();
        
        for (int i = 2; i <= N; ++i)   
             if (D[i] != INF) printf ("%d ", D[i]); else printf ("0 ");
  
        
        return 0;
    }