#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

#define Nmax 50005
int i,n,m,d[Nmax];
const int oo = (1 << 30);
bool InCoada[Nmax]; /// se tine evidenta fiecarui nod care intra in coda, in momentul in care toate sunt in coada dijkstra se opreste
vector < pair < int, int > > G[Nmax]; ///stocheaza perechi de date precum o structura

void citire ()
  {int x,c,y;
     f>>n>>m;
      for(int i=1;i<=n;i++)
      { f>>x>>y>>c;
          G[x].push_back(make_pair(y,c));
      }
  }
 ///
 /// Functia pentru citire ! push_back adauga in G[x] perechiile make_pair y,c;
 ///
void afisare ()
  {  for(int i=2;i<=n;i++)
         if(d[i]!=oo) g<<d[i]<<" ";
            else g<<0<<" ";
  }
///
///
///
  struct comparaDistante
    {
      bool operator () (int x, int y)
         {
             return d[x] > d[y];
         }

    };
    ///Functia care da regula dupa care elementele devin prioritare in priority_queue
priority_queue < int , vector < int > , comparaDistante > Coada; /// COADA PRIORITARA argument INT stocheaza vector si foloseste functia comparaDistante

  void dijkstra (int nodStart)
    {
        for(i=1;i<=n;i++)
           d[i]=oo;
           d[1]=0;
      Coada.push(nodStart); ///adaugam nodul de start in coada;
      InCoada[nodStart]=1; /// marcam nodul de start ca verificat

      while(!Coada.empty()) ///cat timp coada nu este goala
        {int nodCurent = Coada.top(); ///scoatem elementul prioritar
         Coada.pop();  ///reducem lungimea cozii cu elementul curent
         InCoada[nodCurent]=0; ///marcam nodul curent ca neparcurs

                for(unsigned i = 0 ; i < G[nodCurent].size(); i++)
                    { int vecin = G[nodCurent][i].first;
                      int cost  = G[nodCurent][i].second;

                            if(d[nodCurent] + cost < d[vecin])
                                {   d[vecin]=d[nodCurent] + cost; ///inlocuim in caz ca solutia este optima
                                    if(InCoada[vecin]==0)
                                       {Coada.push(vecin); ///adaugam vecinul in coada
                                        InCoada[vecin]=1;  /// marcam vecinul ca verificat
                                       }
                                }
                    }

        }

    }

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