Go: package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	matrix   []int // 隣接行列
	minToMst int   // MSTへの重み最小値
	parent   int   // 最小値の相手
	color    color
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i].matrix = eAtoi((strings.Fields(eGetline(scanner))))
		nodes[i].parent = -1
		nodes[i].minToMst = math.MaxInt16
		nodes[i].color = white
	}

	// 初回はnode[0]がMSTに入るように,minToMstを設定
	nodes[0].minToMst = 0
	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか
		min := math.MaxInt16
		u := -1
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].minToMst < min {
				u = i
				min = nodes[i].minToMst
			}
		}

		if u == -1 {
			break
		}
		// MSTに追加する頂点決定
		nodes[u].color = mst

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みを更新
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].matrix[u] == -1 {
				// 接してない
				continue
			}
			if nodes[i].matrix[u] < nodes[i].minToMst {
				// node[u]との重みが最小
				nodes[i].minToMst = nodes[i].matrix[u]
				nodes[i].parent = u
			}
		}
	}

	sum := 0
	for _, v := range nodes {
		// node[0]はparentが入っていない
		if v.parent != -1 {
			sum += v.matrix[v.parent]
		}
	}
	fmt.Println(sum)
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

C++: #include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
const long long INFLL = 1LL << 60;
const int INFINT = 1 << 30;
const long long MOD = 1e9 + 7;

vector<vector<int>> G(101, vector<int>(0));
vector<int> c(101, 0);
vector<int> d(101, 0);
vector<int> f(101, 0);

template <class T> using vec_alias = ::std::vector<T>;

template <class T> void vecout(T V) {
    auto t = V.begin();
    while(t != V.end()) {
        cout << " " << *t++;
        // if(t != V.end()) cout << " ";
    }
    cout << endl;
};

int t = 0;
void dfs(int i) {
    if(c[i]) return;
    c[i] = 1;
    d[i] = ++t;
    for(auto e : G[i])
        dfs(e);
    f[i] = ++t;
}

class node {
  public:
    int dist = -1;
    vector<int> nex;
};

template <template <class> class Container> class union_find {
  protected:
    class node_type;

  public:
    using container_type = Container<node_type>;
    using size_type = typename container_type::size_type;

  protected:
    class node_type {
      public:
        typename union_find::size_type parent;
        typename union_find::size_type size;
    };

    container_type tree;

  public:
    union_find() : tree() {}
    explicit union_find(const size_type size) : tree(size, {0, 1}) {
        for(size_type i = 0; i < size; ++i)
            tree[i].parent = i;
    }

    bool empty() const { return tree.empty(); }
    size_type size() const { return tree.size(); }

    size_type find(size_type x) {
        assert(x < size());
        while(tree[x].parent != x)
            x = tree[x].parent = tree[tree[x].parent].parent;
        return x;
    }
    bool same(const size_type x, const size_type y) {
        assert(x < size());
        assert(y < size());
        return find(x) == find(y);
    }
    size_type size(const size_type x) {
        assert(x < size());
        return tree[find(x)].size;
    }

    ::std::pair<size_type, size_type> unite(size_type x, size_type y) {
        assert(x < size());
        assert(y < size());
        x = find(x);
        y = find(y);
        if(x != y) {
            if(tree[x].size < tree[y].size) ::std::swap(x, y);
            tree[x].size += tree[y].size;
            tree[y].parent = x;
        }
        return {x, y};
    }
};

class edge {
  public:
    int f;
    int t;
    int c;

    edge() {
        f = -1;
        t = -1;
        c = -1;
    }
    edge(int _f, int _t, int _c) {
        f = _f;
        t = _t;
        c = _c;
    }
};

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, c, t = 0;
    cin >> n;
    union_find<vec_alias> uf(n);
    priority_queue<edge, vector<edge>, greater<edge>> E;

    rep(i, n) rep(j, n) {
        cin >> c;
        if(c > -1) {
            edge tmp(i, j, c);
            E.push(tmp);
        }
    }

    while(!E.empty()) {
        edge e = E.top();
        E.pop();
        if(!uf.same(e.f, e.t)) {
            t += e.c;
            uf.unite(e.f, e.t);
        }
    }
    cout << t << endl;
}

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

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;
    scanf("%d", &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++){
            scanf("%d", &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);
        };
    };

    printf("%d\n", TH.total_weight());

    return 0;
}