// A — Dijkstra. Lazy deletion; the first pop of a node is final.
long[] dijkstra(int n, List<int[]>[] adj, int src) {   // adj[u] = {v, w}
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
    pq.add(new long[]{0, src});
    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        int u = (int) top[1];
        if (top[0] > dist[u]) continue;                // stale entry
        for (int[] e : adj[u]) {
            long nd = dist[u] + e[1];                  // ← the relaxation is the parameter
            if (nd < dist[e[0]]) { dist[e[0]] = nd; pq.add(new long[]{nd, e[0]}); }
        }
    }
    return dist;
}
// Bottleneck variant (778, 1631, 1102): nd = Math.max(dist[u], w)
// Probability variant (1514): max-heap, nd = dist[u] * w, keep the larger

// D — 0-1 BFS. Deque replaces the heap; zero-cost to the front, one-cost to the back.
int[] zeroOneBfs(int n, List<int[]>[] adj, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    Deque<Integer> dq = new ArrayDeque<>();
    dq.addFirst(src);
    while (!dq.isEmpty()) {
        int u = dq.pollFirst();
        for (int[] e : adj[u]) {
            int v = e[0], w = e[1];                    // w is 0 or 1
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.addFirst(v); else dq.addLast(v);
            }
        }
    }
    return dist;
}

// E — Bellman-Ford with at most k edges. The snapshot is mandatory.
int cheapest(int n, int[][] flights, int src, int dst, int k) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int round = 0; round <= k; round++) {
        int[] prev = dist.clone();                     // ← without this, one round
        for (int[] f : flights) {                      //    can chain many edges
            if (prev[f[0]] == Integer.MAX_VALUE) continue;
            dist[f[1]] = Math.min(dist[f[1]], prev[f[0]] + f[2]);
        }
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}
// Drop the k cap and run V-1 rounds for plain Bellman-Ford.
// A V-th round that still improves anything ⇒ a negative cycle.

// F — Floyd-Warshall. k MUST be the outer loop.
void floyd(int[][] d, int n) {                         // d[i][j] preloaded, INF elsewhere
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++) {
            if (d[i][k] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (d[k][j] == INF) continue;
                d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
            }
        }
}

// H — offline queries + DSU sweep.
boolean[] answer(int n, int[][] edges, int[][] queries) {   // q = {u, v, limit}
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    Integer[] order = new Integer[queries.length];
    for (int i = 0; i < order.length; i++) order[i] = i;
    Arrays.sort(order, Comparator.comparingInt(i -> queries[i][2]));

    DSU dsu = new DSU(n);
    boolean[] out = new boolean[queries.length];
    int e = 0;
    for (int qi : order) {                                  // queries in limit order
        while (e < edges.length && edges[e][2] < queries[qi][2]) {
            dsu.union(edges[e][0], edges[e][1]);
            e++;
        }
        out[qi] = dsu.find(queries[qi][0]) == dsu.find(queries[qi][1]);
    }
    return out;                                             // answers in ORIGINAL order
}