An MST question in disguise — “exactly one simple path between any two points” is the definition of a spanning tree, and minimum cost makes it minimum.

Which algorithm, and why. The graph is complete: $n = 1000$ means about $5 \times 10^5$ edges. Kruskal would sort all of them, $O(n^2 \log n)$, which passes but is wasteful. Prim relaxes lazily and never materialises the list. This is the standard dense-versus-sparse call, and it is what the problem is really asking you to make.

Time $O(n^2 \log n)$ as written, from the heap. The classic $O(n^2)$ dense-Prim — scan the bestbest array for its minimum each round instead of using a heap — is actually faster here and worth naming. Space $O(n)$.

• Add the cost when you pop, not when you push. Pushed entries are candidates; popped-and-not-stale ones are real tree edges.
• The stale check if in_tree[u]: continueif in_tree[u]: continue is mandatory with a lazy heap, because a point can be pushed several times at decreasing costs.
• A single point costs 0 and the loop adds one zero. Two points cost their distance.
• Manhattan, not Euclidean. No square roots, so everything stays integral and exact.
• best[0] = 0best[0] = 0 seeds the tree at point 0; any start gives the same total, which is worth saying — MST weight is independent of the root.

Follow-ups you should expect: “Euclidean distance instead?” — the same algorithm, and for points on a plane the MST is a subgraph of the Delaunay triangulation, which gets you to $O(n \log n)$. ”$n = 10^5$?” — $O(n^2)$ is out; you need that geometric structure, or the Manhattan-MST sweep that keeps only $O(n)$ candidate edges. “Which edges?” — record the predecessor whenever you improve best[v]best[v]. “Second-best MST?” — for each tree edge, forbid it and rerun, or use the max-edge-on-path trick. “Some points already connected?” — seed the DSU or mark them all in-tree at cost 0.

The technique is offline query processing: nothing says you must answer queries in the order given, so sort them into the order that makes the work monotone.

Union-find can add edges but never remove them. Processing limits in ascending order means the edge set only ever grows, which is exactly what the structure supports. Each edge is unioned once in total, not once per query — that is where the efficiency comes from.

Time $O(E \log E + Q \log Q + (E + Q) \alpha(n))$. Space $O(n + Q)$.

• Strictly less than the limit. edgeList[e][2] < limitedgeList[e][2] < limit, not <=<=. The third test case — one edge of weight 5, with limits 5 and 6 — exists only to catch this, and it is the single most common wrong submission.
• Sort the indices, not the queries. If you sort the query list itself you lose the mapping back to output positions. Sorting range(len(queries))range(len(queries)) by limit keeps it.
• ee is never reset. It is a single monotone pointer across the whole sweep. Resetting it inside the loop turns the solution quadratic.
• Duplicate edges between the same pair are explicitly allowed; the second union is a harmless no-op.
• Disconnected graphs are fine — find(p) != find(q)find(p) != find(q) simply reports FalseFalse.

Follow-ups you should expect: “Online, answering each query as it arrives?” — build a maximum-spanning-tree-style structure and answer with the minimax path weight: binary lifting on the MST, or a Kruskal reconstruction tree, both giving $O(\log n)$ per query. That is the real answer to “what if you cannot reorder”, and it is the follow-up that separates candidates. “Weight at most the limit?” — change the comparison to <=<=. “Minimise the maximum edge on a path (LC 1631)?” — the same minimax-path idea. “Edges being added and removed?” — offline dynamic connectivity, considerably harder.

Read the definitions as experiments you can run, and the solution writes itself:

• Critical = in every MST = removing it makes the best achievable weight worse (or disconnects the graph entirely).
• Pseudo-critical = in some MST = forcing it in still achieves the baseline weight, and it is not critical.

The n <= 100n <= 100, edges <= 200edges <= 200 constraints are the permission slip: two extra Kruskal runs per edge is at most 400 runs of a near-linear algorithm.

Time $O(E^2 \alpha(n))$ — about $200 \times 400$ union operations. Space $O(n + E)$.

• Carry the original index. You must sort by weight for Kruskal but report by input position. Losing the index is the most common way to get this wrong, and the sorted-tuple trick (w, u, v, i)(w, u, v, i) handles it in one line.
• Disconnection must count as worse, hence returning infinity when fewer than n - 1n - 1 edges were used. Without that, removing a bridge looks free and the edge is misclassified.
• Every edge is critical or pseudo-critical or neither. The elifelif matters: an edge already found critical must not also be listed as pseudo-critical.
• All-equal weights on a cycle make nothing critical and everything pseudo-critical — that is the second test case, and a good sanity check on the elifelif.
• A bridge is always critical, whatever its weight, since without it the graph cannot be spanned.

Follow-ups you should expect: “Faster than $O(E^2)$?” — yes, and this is the real question hiding behind the problem. Run Kruskal weight class by weight class: within a group of equal-weight edges, those that join two different components after all lighter edges are merged are exactly the candidates, and among them the bridges of the contracted multigraph are the critical ones. That gets you to roughly $O(E \log E)$. “Why does grouping by weight work?” — all MSTs use the same number of edges from each weight class, which is the key MST exchange property. “Count the distinct MSTs?” — multiply the spanning-tree counts of the contracted graph per weight class, via Kirchhoff’s matrix-tree theorem. “Is a given edge set extendable to an MST?” — force them all in and compare against the baseline.