1948G - MST with Matching - CodeForces Solution

def get_root(v, fa):
    if fa[v] == v: return v
    fa[v] = get_root(fa[v], fa)
    return fa[v]
n, c = map(int, input().split())
e = [list(map(int, input().split())) for _ in range(n)]
edge = [(e[i][j], i, j) for i in range(n) for j in range(i + 1, n) if e[i][j] > 0]
edge.sort()
inf = float('inf'); ans = inf
for i in range(1, 1 << n):
    now = bin(i).count('1') * c; fa = list(range(n)); tot = n
    for w, u, v in edge:
        if now > ans: break
        if ((i >> u) & 1) or ((i >> v) & 1):
            u = get_root(u, fa); v = get_root(v, fa)
            if u == v: pass
            else: fa[u] = v; now += w; tot -= 1
    if tot == 1: ans = min(ans, now)
print(ans)