Minimum spanning tree (Kruskal) (Union-Find (DSU) Sub-pattern)

// Kruskal's minimum spanning tree: cheapest edges first, skip any edge inside one group.
// Uses the DSU from the Union-Find template. Returns -1 if the graph is not connected.
long long kruskal(int n, vector<array<int, 3>> edges) {   // {weight, u, v}, nodes 0..n-1
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long total = 0;
    int used = 0;
    for (auto& [w, u, v] : edges) {
        if (!dsu.unite(u, v)) continue;            // would close a cycle: never needed
        total += w;
        if (++used == n - 1) break;                // a spanning tree has exactly n - 1 edges
    }
    return used == n - 1 ? total : -1;
}