package templates;

import java.util.*;

class Dijkstra {
  static class Pair {
    int x;
    long y;

    Pair(int x, long y) {
      this.x = x;
      this.y = y;
    }

    @Override
    public String toString() {
      return String.format("(%d, %d)", x, y);
    }
  }

  ArrayList<ArrayList<Pair>> adj;
  long[] d;
  int[] par;
  public static final long INF = (long)1e18;

  public Dijkstra(int n) {
    adj = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      adj.add(new ArrayList<Pair>());
    }
    d = new long[n];
    par = new int[n];
  }

  public void addEdge(int u, int v, long w) {
    --u;
    --v;
    adj.get(u).add(new Pair(v, w));
    adj.get(v).add(new Pair(u, w));
  }

  public void reset() {
    Arrays.fill(d, INF);
    Arrays.fill(par, -1);
  }

  public long[] run(int source) {
    reset();
    --source;
    PriorityQueue<Pair> q = new PriorityQueue<Pair>((a, b) -> {
      if (b.y == a.y) {
        return b.x - a.x;
      }
      return b.y == a.y ? 0 : b.y < a.y ? 1 : -1;
    });
    d[source] = 0;
    q.add(new Pair(source, 0));
    while (!q.isEmpty()) {
      Pair c = q.poll();
      if (c.y != d[c.x])
        continue;
      for (Pair p : adj.get(c.x)) {
        int v = p.x;
        long w = p.y;
        if (d[c.x] + w < d[v]) {
          d[v] = d[c.x] + w;
          par[v] = c.x;
          q.add(new Pair(v, d[v]));
        }
      }
    }
    return Arrays.copyOf(d, d.length);
  }

  public List<Integer> getPath(int s, int t) {
    ArrayList<Integer> path = new ArrayList<Integer>();
    --s;
    --t;
    int c = t;
    while (c != s) {
      path.add(c + 1);
      c = par[c];
    }
    path.add(s + 1);
    Collections.reverse(path);
    return path;
  }
}