One of the algorithms to find the spanning tree is Kruskal’s algorithm, whose outline is as follows:

• Starting from the state where no edge is added to the graph, inspect the edges in ascending order of the weight. If the currently inspecting edge are between vertices \(u\) and \(v\) are not connected yet, add it to the graph.

By managing the connectivity of the graph using a data structure like Disjoint Set Union (DSU), the algorithm runs in a total of \(O(E\log E)\) time, where the sort is the bottleneck. (\(E\) is the number of edges.)

However, in this problem there are at most about \(O((\sum K)^2)\) edges, which prevents from directly applying it in the time limit. Instead, we use the following property about the minimum spanning tree:

• if there is an edge \(e=(u,v)\) that satisfies the following condition, removing edge \(e\) from the candidates does not change the total weight in the minimum spanning tree.
  • there exists a path connecting vertex \(u\) and vertex \(v\) consisting of edges with weights not greater than that of edge \(e\), but not containing edge \(e\).

This can be justified by considering the behavior of Kruskal’s algorithm. (On edge \(e\)’s turn, \(u\) and \(v\) are already connected, so edge \(e\) is never used.) In this problem, the following edges are added:

an edge of weight \(C_i\) connecting vertices \(u\) and \(v\) for all pairs of different vertices \((u, v)\) contained in \(\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace\).

By the property above, it turns out that it is sufficient to add only the following edges:

an edge of weight \(C_i\) connecting vertices \(A_{i,1}\) and \(A_{i,j}\) for each \(j=2,3,\dots,K_i\)a.

This modification reduces the total number of edges to \(O(\sum K)\), allowing to apply Kruskal’s algorithm to solve this problem.

Sample code (C++):

#include <bits/stdc++.h>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> k(m), c(m);
    vector<vector<int>> a(m);
    for (int i = 0; i < m; i++) {
        cin >> k[i] >> c[i];
        a[i].resize(k[i]);
        for (int &j: a[i]) {
            cin >> j;
            --j;
        }
    }
    vector<int> ord(m);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return c[i] < c[j]; });
    dsu uf(n);
    long long ans = 0;
    for (int i: ord) {
        for (int j = 1; j < k[i]; j++) {
            if (uf.same(a[i][0], a[i][j])) continue;
            uf.merge(a[i][0], a[i][j]);
            ans += c[i];
        }
    }
    cout << (uf.groups().size() == 1 ? ans : -1) << endl;
}