#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define Nmax 50005
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m;
const int oo= (1 << 30);
int d[Nmax];
bool InCoada[Nmax];
vector <pair <int , int > > G[Nmax];
struct comparaDistante
{
    bool operator()(int x , int y)
       {
            return d[x]>d[y];
       }
};
priority_queue <int, vector <int> , comparaDistante>Coada;

void citire ()
   {  f>>n>>m;
       for(int i=1;i<=m;i++)
          {  int x,y,c;
              f>>x>>y>>c;
              G[x].push_back(make_pair(y,c));
          }
   }

void dijkstra (int nodStart)
  {
      for(int i=1;i<=n;i++)
         d[i]=oo;
     d[nodStart]=0;
     Coada.push(nodStart);
     InCoada[nodStart]=1;

      while(!Coada.empty())
         {int nodCurent;
          nodCurent = Coada.top();
          Coada.pop();
          InCoada[nodCurent]=0;
              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;
                      if(InCoada[vecin]==0)
                      {
                          InCoada[vecin]=1;
                          Coada.push(vecin);
                      }
                  }
              }
         }

}

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

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