Overview

This problem requires us to first include \(K\) mandatory cables, then complete a spanning tree by adding remaining cables at minimum cost without creating conflicts (cycles) with the mandatory ones.

Analysis

A spanning tree is a structure that “connects \(N\) vertices, contains no cycles, and has exactly \(N-1\) edges.”
Since the specified cables must be used, the constraints are stricter than a standard minimum spanning tree (MST).

The two key observations are:

1. If the mandatory cables alone form a cycle, it’s impossible
   A spanning tree cannot contain cycles. Therefore, if after adding all mandatory cables, an edge connects two vertices already in the same connected component (= creating a cycle), then no valid spanning tree exists and the answer is \(-1\).

2. Minimum cost addition from the state with mandatory cables can be done with Kruskal’s algorithm
   Treat the mandatory cables as “already selected edges,” then examine the remaining edges in ascending order of cost, adopting only those that don’t create cycles. This minimizes the additional cost.
   This works because Kruskal’s algorithm (a greedy method for building MSTs) is optimal as a strategy for “connecting existing connected components at minimum cost.”

Naively “enumerating all spanning trees containing the mandatory edges” would cause combinatorial explosion (since \(M\) can be up to \(2\times10^5\), this is completely infeasible).
Instead, we use Union-Find (DSU) for fast connectivity and cycle detection, incorporating it into the Kruskal’s algorithm framework.

Algorithm

1. Store the input edges (in the form \((W_i, U_i, V_i, i)\), etc.).
2. Manage the set of mandatory edges with a flag array mandatory.
3. Initialize Union-Find.
4. Add all mandatory edges first.
   • For edge \((u,v)\), if union(u,v) fails (already in the same component), the mandatory edges alone create a cycle, so output \(-1\).
   • If successful, add the cost and increment the used edge count used.
5. Sort all edges in ascending order of cost, and examine only non-mandatory edges from smallest cost.
   • If used == N-1, the spanning tree is complete, so stop.
   • Skip edges marked as mandatory (already adopted).
   • If union(u,v) succeeds (doesn’t create a cycle), adopt the edge, add its cost, and used++.
6. At the end, if used != N-1, the graph cannot be made connected (e.g., due to mandatory constraints), so output \(-1\). Otherwise, output the total cost.

(Intuitive picture)
Think of the mandatory edges as forming several “islands (connected components).” Then, by selecting non-mandatory cables from cheapest to most expensive, adopting only those that “connect different islands,” we achieve the minimum cost.

Complexity

• Time complexity: Dominated by sorting, \(O(M \log M)\) (Union-Find operations are nearly \(O(M)\) in total)
• Space complexity: \(O(N+M)\) for edge information and Union-Find

Implementation Notes

• Cycle checking for mandatory edges is the most critical step: If union fails when adding mandatory edges, immediately output \(-1\).

• Don’t double-count mandatory edges: When scanning after sorting, check mandatory[idx] to skip mandatory edges.

• Spanning tree completion check: Determine by whether the number of adopted edges is exactly \(N-1\) (no need for a separate connectivity check).

• Since the input can be large, reading all at once with sys.stdin.buffer.read() as shown in the code improves speed.

  Source Code

import sys

class DSU:
    __slots__ = ("p", "sz")
    def __init__(self, n):
        self.p = list(range(n))
        self.sz = [1] * n

    def find(self, x):
        p = self.p
        while p[x] != x:
            p[x] = p[p[x]]
            x = p[x]
        return x

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a
        self.p[b] = a
        self.sz[a] += self.sz[b]
        return True

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    try:
        N = next(it)
    except StopIteration:
        return
    M = next(it)
    K = next(it)

    U = [0] * (M + 1)
    V = [0] * (M + 1)
    W = [0] * (M + 1)
    edges = []
    for i in range(1, M + 1):
        u = next(it); v = next(it); w = next(it)
        U[i] = u; V[i] = v; W[i] = w
        edges.append((w, u, v, i))

    mandatory = [False] * (M + 1)
    mand_list = []
    for _ in range(K):
        idx = next(it)
        mandatory[idx] = True
        mand_list.append(idx)

    dsu = DSU(N + 1)
    total = 0
    used = 0

    for idx in mand_list:
        u, v, w = U[idx], V[idx], W[idx]
        if not dsu.union(u, v):
            print(-1)
            return
        total += w
        used += 1

    edges.sort(key=lambda x: x[0])
    for w, u, v, idx in edges:
        if used == N - 1:
            break
        if mandatory[idx]:
            continue
        if dsu.union(u, v):
            total += w
            used += 1

    if used != N - 1:
        print(-1)
    else:
        print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.