Dijkstra Algorithm

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f;
using P = pair<int, int>;
int n, m, u, v, w;

void dijkstra(vector<vector<pair<int, int>>>& g,
              vector<int>& dists) {

    priority_queue<P, vector<P>, greater<P>> pq;
    pq.emplace(0, 1);
    dists[1] = 0;
    vector<int> seen(n + 1);

    while (not pq.empty()) {
      const auto [d, u] = pq.top(); pq.pop();
      if (seen[u]) continue;
      seen[u] = 1;

      for (const auto& [v, w] : g[u]) {
        if (seen[v]) continue;
        if (d + w < dists[v]) {
          dists[v] = d + w;
          pq.emplace(d + w, v);
        }
      }
    }
}

int main(int argc, char** argv) {
  cin >> n >> m;
  vector<vector<P>> g(n + 1);
  vector<int> dists(n + 1, INF);
  while (m--) {
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }

  dijkstra(g, dists);

  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (dists[i] == INF) return puts("-1"), 0;
    ans = max(ans, dists[i]);
  }

  return printf("%d\n", ans), 0;
}