GIAOTHONG (DSU)

#include <bits/stdc++.h>
using namespace std;

const int oo = 1e9 + 7;
const int N = 1e6 + 5;
typedef pair <int, int> ii;

struct edge {
    int u, v, c;
};

int n, m, ans;
int parent[N + 5];
vector <edge> e;

bool comp(const edge &a, const edge &b) {
    return a.c < b.c;
}

int get_parent(int u) {
    if (u == parent[u]) return u;
    return parent[u] = get_parent(parent[u]);
}

bool join(int u, int v, int c) {
    u = get_parent(u);
    v = get_parent(v);

    if (u == v) return false;
    parent[v] = u;
    return true;
}

int main(){
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        parent[i] = i;

    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        join(u, v, 0);
    }

    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            int c; cin >> c;
            if (i > j)
                e.push_back({i, j, c});
        }
    }

    sort(e.begin(), e.end(), comp);

    n = e.size();
    ans = 0;

    for (int i = 0; i < n; ++i)
        if (join(e[i].u, e[i].v, e[i].c))
            ans += e[i].c;

    cout << ans;

    return 0;
}