//Se da un graf orientat cu N noduri si M arce.
//Sa se determine lungimea minima a drumului de la nodul 1 la fiecare din nodurile 2, 3, ..., N-1, N si sa se afiseze aceste lungimi.
// Lungimea unui drum este data de suma lungimilor arcelor care constituie drumul.

#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>
#define infinit 0x3f3f3f3f

using namespace std;

void citire(int &n, vector< vector< pair <int, int> > > &la)
{
    ifstream f("dijkstra.in");
    if (!f.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    int m;
    f >> n >> m;
    la.resize(n+1);

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

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

    vector<int> d(n+1, infinit);

    int u, v;
    int w_uv;

    d[sursa] = 0;

    // memo nodurile neselectate, intr-un min heap
    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( const auto &it : la[u] )
      {
          v = it.first;
          w_uv = it.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)
      if (d[i] == infinit)
            g << 0 << ' ';
      else
            g << d[i] << ' ';

    g.close();
}

int main()
{   int n;
    vector< 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;
}