#include <cstdio> 

using namespace std;

#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;   
              if (D[H[d]] > D[H[c]])   
              {   
                  P[H[c]] = d, P[H[d]] = c;   
                  int ax = H[d]; H[d] = H[c], H[c] = ax;
                  c = d;   
              }   
              else c = 1;   
        }   
    }   
  
    void sink(int c)   
    {   
        int d;   
        while (c <= k)   
        {   
            d = c;   
            if (c << 1 <= k)   
            {   
                d = c << 1;   
                if (d < k) if (D[H[d + 1]] < D[H[d]]) ++d;   
            } else return;   
  
            if (D[H[c]] > D[H[d]])   
            {   
                P[H[c]] = d, P[H[d]] = c;   
                int ax = H[d]; H[d] = H[c], H[c] = ax;   
                c = d;   
            } else return;   
        }   
     }   
  
     void solve()   
     {   
         int i;
         for (i = 2; i <= N; ++i)   
             D[i] = INF, P[i] = -1;   
         P[1] = 1, H[++k] = 1;   
  
         while (k)   
         {   
             int min = H[1];   
             int ax = H[1]; H[1] = H[k]; H[k] = ax;   
             P[H[1]] = 1;   
             --k, sink(1);   
             NOD *q = A[min];   
  
             while (q)   
             {   
                 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);      
                 }   
                 q = q->next;   
             }   
         }   
    }   
  
    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;   
    }