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 namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
constexpr int MAX = 101;
constexpr int INF = 1<<21;
enum Color { WHITE = 0, GRAY, BLACK };
int n;
vv(int, M, MAX, MAX, INF);
inline int prim() {
	vi d(n, INF), t(n, -1), color(n, WHITE);
	d[0] = 0;
	int minv, u;
	while(true) {
		minv = INF;
		u = -1;
		rep(i, 0, n) {
			if(minv > d[i] && color[i] != BLACK) {
				u = i;
				minv = d[i];
			}
		}
		if(u == -1) break;
		color[u] = BLACK;
		rep(v, 0, n) {
			if(color[v] != BLACK && d[v] > M[u][v]) {
				d[v] = M[u][v];
				t[v] = u;
				color[v] = GRAY;
			}
		}
	}
	return accumulate(all(d), 0);
;
}
int main() {
	cin >> n;
	int e;
	rep(i, 0, n) {
		rep(j, 0, n) {
			cin >> e;
			if(e != -1) M[i][j] = e;
		}
	}
	P(prim());
	return 0;
}

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;
	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 v = 0; v < n; v++) {
           if(color[v] != BLACK && 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]];
	}
} 

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

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;
	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 v = 0; v < n; v++) {
           if(color[v] != BLACK && 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]];
	}
} 

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();
	
	return 0;
}

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;
    int d[MAX], p[MAX], color[MAX]; 
    // Tに属する頂点とV-Tに属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録
    // MSTにおける頂点vの親を記録
    // 訪問状態を記録

    for(int i=0; i<n; i++){ // 全ての頂点に関して、colorをwhite、dをinftyに初期化
        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 v=0; v<n; v++){
            if(color[v] != BLACK && M[u][v] != INFTY){ // 未訪問かつuからvに辺があるとき
                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(int argc, char const *argv[])
{
    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 <iostream>
#include <utility>
#include <algorithm>
using namespace std;

int p[100];
pair<int, int> a[10000];

int root( int m ) {
	if ( p[m] != m )
		p[m] = root( p[m] );
	return p[m];
}

void unit( int x, int y ) {
	p[root( y )] = root( x );
}

bool same( int x, int y ) {
	return root( x ) == root( y );
}

int main() {
	int n, ai, pn, ans;
	cin >> n;
	for ( int i = 0; i < n * n; i++ ) {
		cin >> ai;
		if ( ai == -1 || i % n <= i / n )
			ai = 2001;
		a[i] = make_pair( ai, i );
	}
	sort( a, a + ( n * n ) );
	pn = 0;
	ans = 0;
	for ( int i = 0; i < n; i++ )
		p[i] = i;
	for ( int i = 0; i < n * n; i++ ) {
		if ( ! same( a[i].second % n, a[i].second / n ) ) {
			ans += a[i].first;
			pn++;
			unit( a[i].second % n, a[i].second / n );
			if ( pn >= n - 1 ) break;
		}
	}
	cout << ans << endl;
}