// Dijkstra's shortest path algorithm with vertex 1 as the source
// Function Arguments:
//   adj: an adjacency list representation of a 1-indexed graph, with each edge represented by a pair (to, weight)
// Return Value: a vector containing the shortest distance from vertex 1 for each vertex, or LLONG_MAX if no path exists
vector<long long> dijkstra(const vector<vector<pair<int, long long>>> &adj) {
  vector<long long> d(adj.size(), LLONG_MAX);
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  d[1] = 0;
  pq.emplace(d[1], 1);
  int counter = 0;
  while (!pq.empty()) {
    long long dv = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    // if (dv > d[v]) {
    //   continue;
    // }
    for (auto &&edge : adj[v]) {
      counter++;
      int to = edge.first;
      long long weight = edge.second;
      if (d[to] > d[v] + weight) {
        d[to] = d[v] + weight;
        pq.emplace(d[to], to);
      }
    }
  }
  return d;
}