No. The spanning tree uses the two cost-2 edges, total installation cost 4. Its A-to-C route costs 4, while the original graph has a direct cost-3 route. Network cost and single-source route cost are different objectives.

When considering the cheapest edge that crosses between current components, take the cut separating one component from the others. Some optimal spanning tree must connect across that cut. If it lacks this cheap edge, add it, creating a cycle, and remove a crossing edge no cheaper than it. Connectivity is preserved and total cost does not increase. Repeating this argument justifies the commitments.

def spanning_tree(n, edges):
    parent, size = list(range(n)), [1] * n
    def find(x):
        while x != parent[x]:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    chosen, total = [], 0
    for u, v, weight in sorted(edges, key=lambda edge: edge[2]):
        a, b = find(u), find(v)
        if a == b:
            continue
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        chosen.append((u, v, weight))
        total += weight
    if n > 0 and len(chosen) != n - 1:
        return None
    return total, chosen

assert spanning_tree(3, [(0, 1, 2), (1, 2, 2), (0, 2, 3)])[0] == 4
assert spanning_tree(3, [(0, 1, 2)]) is None
assert spanning_tree(1, []) == (0, [])

Assume valid integer labels 0..n-1; the empty graph returns an empty result by convention. Edge sorting dominates, giving O(E log E + V) time with near-constant amortized disjoint-set operations, and O(V+E) extra space in this implementation. Equal weights can yield several optimal trees. Negative weights do not break the cut exchange argument.

Prim’s algorithm is a related approach that grows one connected tree by repeatedly choosing a cheapest edge crossing its boundary. Its priority is edge connection cost; Dijkstra prioritizes accumulated route cost.

Analogy limit: directed networks require a different formulation. Do not remove edge directions and assume the resulting spanning tree solves a directed connectivity requirement.

A minimum spanning forest, one minimum spanning tree per connected component. The sample deliberately returns None when a single spanning tree is impossible; a forest API would instead return the selected edges and component information.