Go: package main

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

// Define disjoint-set forests

type vertexNo int

type vertex struct {
	number vertexNo
	rank int
	parent *vertex
}

func makeSet(number vertexNo) vertex {
	return vertex {
		number: number,
		rank: 0,
		parent: nil,
	}
}

func union(x, y *vertex) *vertex {
	return link(findSet(x), findSet(y))
}

func link(x, y *vertex) *vertex {
	if x.rank > y.rank {
		y.parent = x
		return x
	} else {
		x.parent = y
		if x.rank == y.rank {
			y.rank += 1
		}
		return y
	}
}

func findSet(v *vertex) *vertex {
	if v.parent == nil {
		return v
	}
	v.parent = findSet(v.parent)
	return v.parent
}

// Function to calculate minimum spanning tree

type matrix [][]int

type edge struct {
	one vertexNo
	two vertexNo
	weight int
}

const(
	MAX_VERTICES = 100
)

func newEdgesFromMatrix(matrix matrix) []edge {
	edges := make([]edge, 0, MAX_VERTICES * MAX_VERTICES)

	for i := 0; i < len(matrix); i++ {
		row := matrix[i]
		for j := i; j < len(row); j++ {
			if row[j] >= 0 {
				edge := edge{one: vertexNo(i+1), two: vertexNo(j+1), weight: row[j]}
				edges = append(edges, edge)
			}
		}
	}

	return edges
}

func solve(matrix matrix) int {
	nVertices := len(matrix)

	// initialize vertices
	vertices := make([]vertex, nVertices)
	for i := 0; i < nVertices; i++ {
		vertices[i] = makeSet(vertexNo(i+1))
	}

	// prepare edges sorted in the ascending order of weight
	edges := newEdgesFromMatrix(matrix)
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})

	unionCount := 0
	weightSum := 0
	for unionCount < nVertices-1 {
		for i := 0; i < len(edges); i++ {
			edge := edges[i]
			v1 := &vertices[edge.one-1]
			v2 := &vertices[edge.two-1]
			rep1 := findSet(v1)
			rep2 := findSet(v2)
			if rep1.number == rep2.number {
				continue
			}
			union(rep1, rep2)
			edges = append(edges[0:i], edges[i+1:]...)
			weightSum += edge.weight
			unionCount++
			break
		}
	}

	return weightSum
}

// main

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	matrix := parseMatrix(n, sc)

	edges := newEdgesFromMatrix(matrix)
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})

	fmt.Println(solve(matrix))
}

func parseMatrix(n int, sc *bufio.Scanner) [][]int {
	matrix := make([][]int, n)
	for i := 0; i < n; i++ {
		matrix[i] = make([]int, n)
		for j := 0; j < n; j++ {
			x, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			matrix[i][j] = x
		}
	}
	return matrix
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextInt(sc *bufio.Scanner) (int, error) {
	return strconv.Atoi(nextText(sc))
}

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


// ????????????union-find tree
int P[10010];
void init(int N){
  for(int i=0; i<=N; i++){
    P[i] = i;
  }
}

int root(int a) {
  if(P[a]==a)return a; // a???root
  return (P[a] = root(P[a])); // a?????????root????±????, a????????¨??????
}
bool is_same_set(int a, int b){ // a??¨b???????????°?????????????±?????????????
  return root(a) == root(b);
}
void unite(int a, int b){ // a??¨b???????????°?????????????????¨??????
  P[root(a)] = root(b);
}
// ???????????§???union-find tree


int main(){
  int n;
  cin >> n;
  pair<int,int> E[1000010];
  int a;
  int k=0;
  int m=0;
  int S[10010], G[10010];
  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      cin >> a;
      E[k].first = a; // ????????????
      E[k].second = m; // ????????????
      S[m] = i;
      G[m] = j;
      k++;
      m++;
      
    }
  }
    
#if 0
  for(int i=0; i<n*n; i++){
    cout << E[i].first << " " << E[i].second;
    cout << " -> " << S[E[i].second] << " " << G[E[i].second] << endl;
  }
#endif


  sort(E, E+n*n);

#if 0
  cout << endl;
  for(int i=0; i<n*n; i++){
    cout << E[i].first << " " << E[i].second;
    cout << " -> " << S[E[i].second] << " " << G[E[i].second] << endl;
  }
#endif
  
  
  int T = 0; // ?£?T????????????
  init(n); // ??¢??°??????, ?????°??????????????°

  for(int i=0; i<n*n; i++){
    if(E[i].first!=-1){
      if(is_same_set(S[E[i].second],G[E[i].second])==0){
	T += E[i].first;
	unite(S[E[i].second],G[E[i].second]);
      }
    }
    
  }

  cout << T << endl;
}

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

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

int n, M[MAX][MAX];

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

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

  d[0] = 0;

  while ( 1 )
  {
    minv = INFTY;
    u = -1;
    for ( int i = 0; i < n; i++ )
    {
      if ( minv > d[i] && color[i] != BLACK )
      {
        u = i;
        minv = d[i];
      }
    }
    if (u == -1) break;
    color [u] = BLACK;
    for (int k = 0; k < n; k++ )
    {
      if ( color[k] != BLACK && M[u][k] != INFTY )
      {
        if( d[k] > M[u][k] )
        {
          d[k]=M[u][k];
          p[k]=u;
          color[k] = 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;
  return 0;
}

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;
}