#include<iostream> 
#include<iterator>
#include<vector>
#include<list>
#include<queue>
#include<fstream>
#include<algorithm>

// #include "CountSort.h";
// #include "BinarySearch.h";
// #include "Tree.h"
// #include "RabinKarp.h"
// #include "Dijkstra.h"

using namespace std;

int Search(const string& str, const string& substr)
{
  return -1;
}

struct edge
{
  int nextNode{};
  int cost{};
};

vector<int> Dijkstra(const vector<list<edge>>& graph, int initialNode)
{
  vector<int> costs(graph.size(), numeric_limits<int>::max());
  costs[initialNode] = 0;

  priority_queue<int> heap;
  heap.push(initialNode);

  while (!heap.empty())
  {
    auto node = heap.top();
    heap.pop();

    for (const auto& edge : graph.at(node))
    {
      if (costs[node] + edge.cost < costs[edge.nextNode])
      {
        costs[edge.nextNode] = costs[node] + edge.cost;
        heap.push(edge.nextNode);
      }
    }
  }

  return costs;
}

int main()
{
  // string str = "You'll #neversea algorithms like these";
  // string substr = "neversea";
  // 
  // int pos = Search(str, substr);
  // if (pos != -1)
  // {
  //   cout << "Subsirul a fost gasit pe pozitia : " << pos << endl;
  // }
  // else
  // {
  //   cout << "Subsirul nu a fost gasit" << endl;
  // }


  // read input data
  ifstream in("dijkstra.in");
  
  int nodesCount{};
  int edgesCount{};

  in >> nodesCount;
  in >> edgesCount;

  vector<list<edge>> graph(nodesCount + 1, list<edge>{});
  for (int i = 0; i < edgesCount; ++i)
  {
    int from{}, to{}, cost{};
    in >> from >> to >> cost;

    graph[from].push_back({ to, cost });
    //graph[to].push_back({from, cost});
  }

  // run dijkstra
  auto costs = Dijkstra(graph, 1);

  // write output data
  ofstream out("dijkstra.out");
  for (int i = 2; i < costs.size(); ++i)
    out << costs[i] << " ";
}