#include <fstream>
#include <queue>

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int infinit = (1 << 31) - 1;

struct nod
{
     int info;
     int cost;
     nod *adr;
} *v[50005];

void adaugare (int x, int y, int z)
{
     nod *c = new nod;
     c -> info = y;
     c -> cost = z;

     c -> adr = v[x];
     v[x] = c;
}

int n, m, best[50005];

void citire ()
{
     int a, b, c;

     f >> n >> m;

     for (int i = 1; i <= m; i ++)
     {
          f >> a >> b >> c;
          adaugare (a, b, c);
     }

     for (int i = 2; i <= n; i ++)
          best[i] = infinit;
}

queue < pair < int, int> > Q;

void dijkstra ()
{
     int nod_curent, cost_curent, next;

     Q.push (make_pair (1, 0));

     while (! Q.empty ())
     {
          nod_curent = (Q.front ()).first;
          cost_curent = (Q.front()).second;

          Q.pop ();

          nod *c = v[nod_curent];

          while (c)
          {
               next = c -> info;

               if (cost_curent + c -> cost < best[next])
               {
                    best[next] = cost_curent + c -> cost;
                    Q.push (make_pair (next, cost_curent + c -> cost));
               }

               c = c -> adr;
          }
     }
}

void afisare ()
{
     for (int i = 2; i <= n; i ++)
          if (best[i] != infinit)
               g << best[i] << " ";
          else
               g << 0 << " ";
}

int main()
{
     citire ();
     dijkstra ();
     afisare ();

     f.close ();
     g.close ();
     return 0;
}