#include <cstdio>
#include <fstream>

using namespace std;

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define MAX_N 50005
#define INF 200000000

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

int N, M, S;

int D[MAX_N];
int Q[MAX_N];
unsigned char ST[MAX_N];

const int MOD = 50000;

NOD *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 = P[x], P[x] = q;
           }
      }    
      
      void BFord () 
      {
           int i, li, lf;
           S = 1, li = lf = 0;
           Q[++lf] = S;
           
           for (i = 1; i <= N; ++i) D[i] = INF;
           D[S] = 0;
           ST[S] = 1;
           
           while (li < lf)
           {
                 int q = Q[(++li)%MOD];
                 ST[q] = 0;
                 for (NOD *p = P[q]; p != NULL; p = p->next)
                     if (D[p->nod] > D[q] + p->cost)
                     {
                        D[p->nod] = D[q] + p->cost;
                        if (ST[p->nod] != 1)
                           Q[(++lf)%MOD] = p->nod, ST[p->nod] = 1;
                     }
           }
           for (i = 2; i <= N; ++i)
               if (D[i] == INF) printf ("0 ");
                  else printf ("%d ", D[i]);             
      }  

      int main ()
      {
          freopen (FIN, "r", stdin);
          freopen (FOUT, "w", stdout);
          
          readdata ();
          BFord();
          
          return 0;
      }