Go: package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	I int
	J int
	A int
}

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]int, n)
	edges := make([]Edge, 0, n*(n-1)/2)
	parents := make([]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&g[i][j])
			if g[i][j] >= 0 {
				edges = append(edges, Edge{i, j, g[i][j]})
			}
		}
		parents[i] = i
	}
	sort.SliceStable(edges, func(i, j int) bool { return edges[i].A >= edges[j].A })

	sum := 0
	num := 0
	for len(edges) > 0 && num < n-1 {
		edge := edges[len(edges)-1]
		edges = edges[:len(edges)-1]

		if same(edge.I, edge.J, &parents) {
			continue
		}
		union(edge.I, edge.J, &parents)
		sum += edge.A
		num += 1
	}
	fmt.Println(sum)
}



func root(id int, parents *[]int) int {
	if id == (*parents)[id] {
		return id
	}
	return root((*parents)[id], parents)
}

func union(i, j int, parents *[]int) {
	(*parents)[root(j, parents)] = (*parents)[root(i, parents)]
}

func same(i, j int, parents *[]int) bool {
	return root(i, parents) == root(j, parents)
}

C++: #include <bits/stdc++.h>
#define rep(i,a) for(i=0;i<a;i++)
using namespace std;
static const int W = 0;
static const int G = 1;
static const int B = 2;

int prim(int n, vector<vector<int> > &M) {
    int i,u,min,total;
    vector<int> d(n);
    vector<int> p(n);
    vector<int> color(n);

    rep(i,n){
        d[i] = INT_MAX;
        p[i] = -1;
        color[i] = W;
    }
    d[0] = 0;
    while(true){
        min = INT_MAX;
        u = -1;
        rep(i,n){
            if(min > d[i] && color[i] != B) {
                u = i;
                min = d[i];
            }
        }
        if(u==-1) break;
        color[u] = B;
        rep(i,n){
            if(color[i] != B && M[u][i])
                if(d[i] > M[u][i]) {
                    d[i] = M[u][i];
                    p[i] = u;
                    color[i] = G;
                }
        }
    }
    rep(i,n){
        if(p[i] != -1) total += M[i][p[i]];
    }
    return total;
}

int main(void) {
    int i,j,n,total = 0;
    vector<vector<int> > M;
    cin >> n;
    M.resize(n);

    rep(i,n){
        M[i].resize(n);
    }
    rep(i,n){
        rep(j,n){
            cin >> M[i][j];
            if(M[i][j] == -1) M[i][j] = INT_MAX;;

        }
    }
    total = prim(n,M);
    cout << total << endl;
    return 0;
}

C++: #include <iostream>

using namespace std;

const int MAX=100;
const int INFTY=(1<<21);
const int WHITE=0;
const int GRAY=1;
const int BLACK=2;

int M[MAX][MAX];
int n;

int prim(){
    int u,minv;
    int color[MAX],d[MAX],p[MAX];

    for(int i=0;i<n;i++){
        d[i]=INFTY;
        p[i]=-1;
        color[i]=WHITE;
    }

    d[0]=0;

    while(true){
        minv=INFTY;
        u=-1;
        for(int i=0;i<n;i++){
            if(minv>d[i] and color[i]!=BLACK){
                u=i;
                minv=d[i];
            }
        }
        if(u==-1) break;
        color[u]=BLACK;
        for(int v=0;v<n;v++){
            if(color[v]!=BLACK and M[u][v]!=INFTY){
                if (d[v]>M[u][v]){
                    d[v]=M[u][v];
                    p[v]=u;
                    color[v]=GRAY;
                }
            }
        }
    }
    int sum=0;
    for(int i=0;i<n;i++){
        if(p[i]!=-1)sum+=M[i][p[i]];
    }

    return sum;
}

int main()
{
    cin>>n;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int e; cin>>e;
            M[i][j]= (e==-1)? INFTY:e;
        }
    }
    cout<<prim()<<endl;
}

C++: #include <iostream>
#include <vector>
#include <cstdlib>
#include <utility>
#include <algorithm>

using namespace std;

vector<int> djset, szset;
vector<pair<int, pair<int, int>>> G;

int root(int x)
{
    int v = djset[x];
    while (v != djset[v]) v = djset[v];
    djset[x] = v;
    return v;
}

int main(void)
{
    int N;
    cin >> N;
    G.resize(N * N);
    int count = 0;
    int temp;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> temp;
            if (i == j || temp == -1) continue;
            G[count++] = make_pair(temp, make_pair(i, j));
        }
    }
    djset.resize(count);
    szset.resize(count, 1);
    G.erase(G.begin() + count, G.end());
    sort(G.begin(), G.end());
    for (int i = 0; i < count; i++) djset[i] = i;
    int v[2], r[2];
    int ans = 0;
    for(auto i : G)
    {
        v[0] = i.second.first;
        v[1] = i.second.second;
        for (int i = 0; i < 2; i++) r[i] = root(v[i]);
        if (r[0] == r[1]) continue;
        if (szset[r[1]] > szset[r[0]]) swap(r[0], r[1]);
        djset[r[1]] = r[0];
        szset[r[0]] += szset[r[1]];
        szset[r[1]] = 0;
        ans += i.first;
    }
    cout << ans << endl;
    return 0;
}