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
	for len(edges) > 0 {
		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
	}
	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++: #define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
#include<queue>
#include<iomanip>
#include<set>
#include<map>
#include<utility>
#include<string>
#include<vector>

using namespace std;

#define LL long long
const int dx[4] = { 1,-1,0,0 };
const int dy[4] = { 0,0,1,-1 };
bool OOA(int x, int y, int H, int W) { return (0 <= x && x<H) && (0 <= y && y<W); }

struct UnionFind {
	int V;
	vector<int>ne;
	void init() { for (int i = 0;i<V;i++)ne.push_back(i); };

	int root(int x) {
		if (ne[x] == x)return x;
		return ne[x] = root(ne[x]);
	}
	bool same(int x, int y) { return root(x) == root(y); }
	void unite(int x, int y) {
		if (same(x, y))return;
		if (x>y)swap(x, y);
		ne[ne[y]] = ne[x];
		return;
	}
};

struct Edge{
	int fr,to,val;
	bool operator < (Edge x){
		return (val<x.val);
	}
};

vector<Edge>e;
int n;

int MST() {//最小全域木の重みの総和
	int ret = 0;
	UnionFind uf;
	uf.V = n;
	uf.init();
	sort(e.begin(), e.end());
	for (int i = 0;i<e.size();i++) {
		if (uf.same(e[i].fr, e[i].to))continue;
		ret += e[i].val;
		uf.unite(e[i].fr, e[i].to);
	}
	return ret;
}


int main() {
	cin >> n;
	e = vector<Edge>(n);
	for (int i = 0;i<n;i++) {
		for (int j = 0;j<n;j++) {
			int a;
			cin >> a;
			if (a != -1) e.push_back({ i,j,a });
		}
	}

	cout << MST() << endl;
	return 0;
}

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

using Weight = int;
using Capacity = int;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src_, int dst_, int weight_) :
        src(src_), dst(dst_), weight(weight_) { }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

bool operator < (const Edge &e, const Edge &f){ return e.weight > f.weight; }
pair<Weight, Edges> prim(const Graph &g, int r = 0) {
    Edges T; Weight total = 0; vector<int> vis(g.size());
    priority_queue<Edge> q;
    q.emplace(-1, r, 0);
    while (!q.empty()) {
        Edge e = q.top(); q.pop();
        if (vis[e.dst]) continue;
        vis[e.dst] = true;
        total += e.weight; if(e.src != -1) T.push_back(e);
        for(auto& f : g[e.dst]) if (!vis[f.dst]) q.push(f);
    }
    return make_pair(total, T);
}

int main(){
    int n;
    cin >> n;
    Graph g(n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int x;
            cin >> x;
            if(x != -1) g[i].emplace_back(i,j,x);
        }
    }
    cout << prim(g).first << endl;
}

C++: // ALDS1_12_A.cpp
// Graph II - Minimum Spanning Tree
#include <iostream>
using namespace std;

const int maxN = 100;
const int INF = 2001;
int w[maxN][maxN];
int color[maxN];
int n;
static const int WHITE = 0;
static const int BLACK = 1;

int prim(int x)
{
    int res = 0;
    int cnt = 1;
    color[x] = BLACK;
    while (cnt++ != n) {
        int minCost = INF;
        int pos = 0; // ??°?????°?????????
        for (int i = 0; i < n; i++) {
            if (color[i] != BLACK) continue;
            for (int j = 0; j < n; j++) {
                if (color[j] != WHITE) continue;
                if (w[i][j] < minCost) {
                    pos = j;
                    minCost = w[i][j];
                }
            }
        }
        res += minCost;
        color[pos] = BLACK;
    }
    return res;
}

int main()
{
    cin >> n;
    int num;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> num;
            if (num == -1) w[i][j] = INF;
            else w[i][j] = num;
        }
    }
    cout << prim(0) << endl;
    return 0;
}

C++: #include<iostream>
using namespace std;

class union_find  // union find.
{
	int* U;
public:
	union_find(int n){ U = new int [n + 1]; for(int i = 1; i <= n; i++) U[i] = i; }
	int root(int a){ if(U[a] == a){ return a; } U[a] = root(U[a]); return U[a]; }
	bool same(int a, int b){ return root(a) == root(b); }
	void join(int a, int b){ int x = root(a), y = root(b); U[x] = y; }
	~union_find(){ delete [] U; }
};

struct edge{ int v1, v2; int weight; };  // edge.

edge init(){
	edge e;
	e.v1 = 0; e.v2 = 0; e.weight = -1;
	return e;
}

edge init(int a, int b, int w){
	edge e;
	e.v1 = a; e.v2 = b; e.weight = w;
	return e;
}

void swap_e(edge e1, edge e2)
{
	swap(e1.v1, e2.v1); swap(e1.v2, e2.v2); swap(e1.weight, e2.weight);
}

class edge_heap  // heap.
{
	edge* E;
	int edge_n;
public:
	edge_heap(int n){ E = new edge [n + 1]; edge_n = 0; }
	void min_heap(int i);
	void insert_heap(edge e);   // sorting.
	void insert_nl(edge e);     // no sorting.
	edge delete_min();
	bool isEmpty(){ return edge_n == 0; }
	int total_weight();
	~edge_heap(){ delete [] E; }
};

void edge_heap::min_heap(int i)
{
	int l = 2 * i, r = 2 * i + 1;
	if(l > edge_n && r > edge_n) return;
	int minid = i;
	if(l <= edge_n){ if(E[l].weight < E[minid].weight) minid = l; }
	if(r <= edge_n){ if(E[r].weight < E[minid].weight) minid = r; }
	if(minid == i) return;
	swap(E[minid], E[i]);
	min_heap(minid);
}

void edge_heap::insert_heap(edge e)
{
	edge_n++;
	int w = e.weight;
	int i = edge_n;
	while(i > 1){
		if(w < E[i / 2].weight){
		E[i] = E[i / 2];
		}else{ break; }
		i /= 2;
	};
	E[i] = e;
}
void edge_heap::insert_nl(edge e){ edge_n++; E[edge_n] = e; }

edge edge_heap::delete_min()
{
	edge e = E[1];
	E[1] = E[edge_n]; edge_n--;
	min_heap(1);
	return e;
}

int edge_heap::total_weight()
{
	int tw = 0;
	for(int i = 1; i <= edge_n; i++) tw += E[i].weight;
	return tw;
}

int main()
{
	int n, i, j, w;
	cin >> n;
	edge_heap EH(n * (n + 1) / 2); // All Edge heap.
	edge e;

	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			cin >> w;
			if(j <= i || w < 0) continue;
			e = init(i, j, w);
			EH.insert_heap(e);
		}
	}

	edge_heap TH(n);   // Tree heap.

	union_find VG(n);  // vertex group.

	while(!EH.isEmpty()){
		e = EH.delete_min();
		if(!VG.same(e.v1, e.v2)){
			VG.join(e.v1, e.v2);
			TH.insert_nl(e);
		};
	};

	cout << TH.total_weight() << endl;

	return 0;
}