struct Edge {
  int to, cost;

  bool operator<(const Edge &b) const {
    return cost > b.cost; // 우선순위 큐의 top이 최소값이 되도록
  }
};

vector<vector<Edge>> graph;
vector<int> costs; // 처음에 INFINITY로 초기화해야함

void dijkstra(int start, vector<vector<Edge>> &graph, vector<int> &costs) {
  priority_queue<Edge> pq;

  fill(costs.begin(), costs.end(), INFINITY);

  pq.push({0, start, 0});
  while (!pq.empty()) {
    Edge cur = pq.top();
    pq.pop();

    for (Edge next : graph[cur.to]) {
      int new_val = costs[cur.to] + next.cost;
      int before_val = costs[next.to];

      if (new_val < before_val) {
        costs[next.to] = new_val;
        pq.push({next.to, new_val});
      }
    }
  }
}

priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > pq;

// 아래 header를 추가해서 compare함수를 만들 수 있다.
#include <functional>	// to use greater<>
greater<> // compare