Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

type ElementKey int
type Node struct {
	key    ElementKey
	parent *Node
	rank   int
}

func newNode(key ElementKey) *Node {
	node := Node{}
	node.key = key
	node.parent = &node
	node.rank = 0

	return &node
}

func union(x, y *Node) {
	xSet := findSet(x)
	ySet := findSet(y)
	link(xSet, ySet)
}

func link(x, y *Node) {
	if x.rank > y.rank {
		y.parent = x
	} else {
		x.parent = y

		if x.rank == y.rank {
			y.rank++
		}
	}
}

func findSet(x *Node) *Node {
	if x != x.parent {
		x.parent = findSet(x.parent)
	}
	return x.parent
}

func newDisjointSets(nSets int) *DisjointSets {
	sets := DisjointSets{}
	sets.keyToNode = map[ElementKey]*Node{}
	for i := 0; i < nSets; i++ {
		key := ElementKey(i)
		sets.keyToNode[key] = newNode(key)
	}
	return &sets
}

type DisjointSets struct {
	keyToNode map[ElementKey]*Node
}

func (sets *DisjointSets) union(x, y ElementKey) {
	xNode := sets.keyToNode[x]
	yNode := sets.keyToNode[y]
	union(xNode, yNode)
}

func (sets DisjointSets) findSet(x ElementKey) *Node {
	xNode := sets.keyToNode[x]
	return findSet(xNode)
}

type Edge struct {
	i, j   int
	weight int
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	sets := newDisjointSets(n)
	edges := []Edge{}
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, n)
		for j := 0; j < n; j++ {
			a[i][j] = nextInt()
			if a[i][j] >= 0 {
				e := Edge{
					i:      i,
					j:      j,
					weight: a[i][j],
				}
				edges = append(edges, e)
			}
		}
	}
	sort.Slice(edges, func(i, j int) bool { return edges[i].weight < edges[j].weight })
	totalWeight := 0
	for _, edge := range edges {
		i := ElementKey(edge.i)
		j := ElementKey(edge.j)
		if sets.findSet(i) != sets.findSet(j) {
			totalWeight += edge.weight
			sets.union(i, j)
		}
	}
	fmt.Println(totalWeight)
}

C++: #include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define PI 3.14159265358979323846
#define vll vector<long long>
using namespace std;
using ll = long long;
using ld = long double;

// -------------------------------------------------
class UnionFind {
private:
  ll n;
  vll P;
  ll root(ll x);
  void setN(ll N);
  void init();

public:
  UnionFind(ll N);
  void unite(ll x, ll y);
  bool same(ll x, ll y);
};

// コンストラクタ
UnionFind::UnionFind(ll N) {
  setN(N);
  init();
}

// nを変更
void UnionFind::setN(ll N) { n = N; }

// Union-Find Treeを初期化する
void UnionFind::init() {
  P.clear();
  rep(i, n) { P.push_back(i); }
}

// 根の値を返す
ll UnionFind::root(ll x) {
  if (P[x] == x) { return x; }
  return (P[x] = root(P[x])); // パス圧縮しつつ返す
}

// 木を結合する（rankはとりあえず無視）
void UnionFind::unite(ll x, ll y) { P[root(x)] = root(y); }

// xとyが同じ集合にあるか判別
bool UnionFind::same(ll x, ll y) {
  if (root(x) == root(y)) {
    return true;
  } else {
    return false;
  }
}
// -------------------------------------------------

// ----本問について----
// 問題：最小全域木
// 問題文URL：https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_12_A
// 所要時間：
// 学んだこと：
// ------------------

// ----ここから本問のソースコード----

struct edge {
  ll w, s, e; // weight, start, end

  edge(ll W, ll S, ll E) {
    w = W;
    s = S;
    e = E;
  }
};

bool cmpI(const edge &a, const edge &b) { return a.w < b.w; }

// グローバル変数（入力）
ll n;
vector<vll> A;

// 隣接行列から辺の情報を取り出す
vector<edge> MakeEdges() {
  vector<edge> edges;
  rep(i, n) {
    for (ll j = i + 1; j < n; j++) {
      if (A[i][j] != -1) { edges.push_back(edge(A[i][j], i, j)); }
    }
  }
  return edges;
}

// 入力
void input() {
  cin >> n;
  rep(i, n) {
    vll a(n);
    rep(j, n) { cin >> a[j]; }
    A.push_back(a);
  }
}

// 最小全域木の重みの合計を求める（クラスカル法）．
void solve() {
  vector<edge> edges = MakeEdges();
  // 辺を重みをキーに昇順ソート
  sort(edges.begin(), edges.end(), cmpI);
  UnionFind u(n);
  ll ans = 0;
  rep(i, edges.size()) {
    if (!u.same(edges[i].s, edges[i].e)) { // 閉路ができない
      u.unite(edges[i].s, edges[i].e);
      ans += edges[i].w;
    }
  }
  cout << ans << endl;
}

int main() {
  input();
  solve();
  return 0;
}

C++: #include <queue>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	vector<vector<short>> dist(n, vector<short>(n));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			scanf("%hd", &dist[i][j]);
			dist[i][j] = dist[i][j] < 0 ? 10000 : dist[i][j];
		}
	}
	
	vector<bool> visited(n, false);
	priority_queue<pair<short,int>, vector<pair<short,int>>, greater<pair<short,int>>> q;
	q.push(make_pair(0, 0));
	
	int ans = 0;
	while(q.size()){
		pair<short,int> edge = q.top();
		q.pop();
		if(visited[edge.second]) continue;
		ans += edge.first;
		visited[edge.second] = true;
		for(int i = 0; i < n; i++){
			if(!visited[i]){
				q.push(make_pair(dist[i][edge.second], i));
			}
		}
	}
	
	printf("%d\n", ans);
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef	tuple<int,int,int>T;
typedef vector<T>VT;
int main(void){
	int n;
	int box[101][101];
	int i,j;
	int per[101];
	int ran[101];
	int x,y;
	int sum;
	VT v;
	cin>>n;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			cin>>box[i][j];
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(box[i][j]!=-1){
				v.push_back(make_tuple(box[i][j],i,j));
			}
		}
	}
	sort(v.begin(),v.end());
	for(i=1;i<=n;i++){
		per[i]=i;
		ran[i]=1;
	}
	sum=0;
	for(i=0;i<v.size();i++){
		x=get<1>(v[i]);
		y=get<2>(v[i]);
		while(x!=per[x])	x=per[x];
		while(y!=per[y])	y=per[y];
		if(x!=y){
			sum+=get<0>(v[i]);
			if(ran[x]>ran[y])		per[y]=x;
			else if(ran[x]<ran[y])	per[x]=y;
			else{
				per[x]=y;
				ran[x]++;
			}
		}
	}
	cout<<sum<<endl;
	return 0;
}

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

int n;
int g[101][101];

int d[101];
char c[101];
int p[101];

void prim() {
    for (int i = 0; i < n; ++i) {
        d[i] = INT_MAX;
        c[i] = 'w';
    }
    c[0] = 'b';
    d[0] = 0;
    while (true) {
        int u, v;
        int mine = INT_MAX;
        for (int j = 0; j < n; ++j) {
            if (c[j] == 'b') {
                u = j;
                for (int k = 0; k < n; ++k) {
                    if(g[u][k] > -1 && g[u][k] <= d[k] && c[k] != 'b' && g[u][k] <= mine) {
                        d[k] = g[u][k];
                        mine = d[k];
                        v = k;
                    }
                }
            }
        }
        p[v] = u;
        c[v] = 'b';
        if(mine == INT_MAX) break;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int w;
            cin >> w;
            g[i][j] = w;
        }
    }
    prim();
    int sum = 0;
    for (int k = 0; k < n; ++k) {
        sum += d[k];
    }
    cout << sum << endl;


    return 0;
}