#include <fstream>
#include <vector>
#include <set>

#define infinit 0x3f3f3f3f

using namespace std;

// pt min heap - functia de comparare

struct muchie_min{

  int d;

  bool operator < (const muchie_min& m) const
  {
    return d < m.d;
  }
};

struct comparator_muchie_min
{
  bool operator () (const muchie_min& m1, const muchie_min& m2) const
  {
      return m1.d < m2.d;
  }
};

void citire(int &n, vector< pair <int, int> >* &la)
{
    ifstream f("dijkstra.in");
    int m, x, y;
    int c;

    f >> n >> m;

    //memo G prin lista de muchii
    la = new vector< pair <int, int> >[n+1];

    for(int i=1; i<=m; i++)
    {
        f >> x >> y >> c;
        la[x].push_back( {y, c} );
    }
    f.close();
}

void Dijkstra(int n, vector< pair <int, int> >*la, int sursa)
{

    int *d = new int [n+1];

    int u, v;
    int w_uv;

    for(int i=0; i<n; i++)
    {
      d[i] = infinit;
    }


    d[sursa] = 0;

    // memo nodurile neselectate intr-un min heap
    //set< muchie_min, comparator_muchie_min> Q;
    set < pair <int, int> > Q;
    Q.insert( {0, sursa} );

    while( !Q.empty() )
    {
      pair<int, int> tmp = *(Q.begin());
      Q.erase( Q.begin() );
      u = tmp.second;

      for(int i=0; i< la[u].size(); i++)
      {
          v = la[u][i].first;
          w_uv = la[u][i].second;

          if( (d[u] + w_uv) < d[v] )
          {
            if(Q.find({d[v] , v}) != Q.end())
                Q.erase( Q.find( {d[v] , v} ) );

            d[v] = d[u] + w_uv;
            Q.insert( {d[v], v} );
          }
      }
    }

    ofstream g("dijkstra.out");
    for(int i=2; i<=n; i++)
        g << d[i] << " ";
    g.close();

 delete []d;
}

int main()
{   int n;
    vector< pair <int, int> > *la;

    citire(n, la);

//    for(int i=1; i<=n; i++)
//    {
//       cout << i << ": ";
//       for(int j=0; j<la[i].size(); j++)
//          cout << la[i][j].first << "/" << la[i][j].second << " ";
//       cout << endl;
//    }

    Dijkstra(n, la, 1);

    return 0;
}