Go: package main

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

//util
var sc = bufio.NewScanner(os.Stdin)

func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func printList(list []int) {
	n := len(list)
	buf := bufio.NewWriter(os.Stdout)
	for _, v := range list[0 : n-1] {
		buf.Write([]byte(fmt.Sprintf("%d ", v)))
	}
	buf.Write([]byte(fmt.Sprintf("%d\n", list[n-1])))
	buf.Flush()
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

//solve
const (
	MAX   = 100
	INFTY = (1 << 21)
	WHITE = 0
	GRAY  = 1
	BLACK = 2
)

//V: グラフの頂点全体の集合
//T: MSTに属する頂点の集合
var (
	n     int
	M     [MAX][MAX]int //重みを記録する隣接行列
	color [MAX]int
	p     [MAX]int //MSTにおける頂点の親を記録
	d     [MAX]int //Tに属する頂点と、V−Tに属する頂点を繋ぐ辺の中で、重みが最小のものを記録
)

func prim() int {
	var u, minv int
	//初期化
	for i := 0; i < n; i++ {
		d[i] = INFTY
		p[i] = -1
		color[i] = WHITE
	}

	d[0] = 0

	for {
		//頂点uを決めていく
		//つまり、Tに属する頂点と、V−Tに属する頂点を繋ぐ辺の中で、重みが最小のものを決める
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			//未訪問かつ、辺の重みが最小となるuを選ぶ
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK
		for 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
				}
			}
		}
	}

	sum := 0
	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += M[i][p[i]]
		}
	}
	return sum
}

func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {

		for j := 0; j < n; j++ {
			tmp := nextInt()
			if tmp == -1 {
				tmp = INFTY
			}
			M[i][j] = tmp
		}

	}

	fmt.Println(prim())

}

C++: #define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream &operator << (ostream &os, const vector<T> &);
template<size_t n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, const tuple<T...> &){}
template<size_t n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream &os, const tuple<T...> &t){
    os << (n == 0 ? "" : " ") << get<n>(t); _ot<n+1>(os, t);
}
template<class...T> ostream &operator << (ostream &os, const tuple<T...> &t){
    _ot<0>(os, t); return os;
}
template<class T, class U> ostream & operator << (ostream &os, const pair<T,U> &p){
    return os << "(" << p.first << ", " << p.second << ") ";
}
template<class T> ostream &operator << (ostream &os, const vector<T> &v){
    for(size_t i = 0; i < v.size(); i++) os << v[i] << (i + 1 == v.size() ? "" : ", "); return os;
}
#ifdef DEBUG
#define dump(...) (cerr << #__VA_ARGS__ << " = " << make_tuple(__VA_ARGS__) \
                   << " (L : " << __LINE__ << ")" << endl)
#else
#define dump(...)
#endif
#define all(c) begin(c), end(c)
#define range(i,a,b) for(int i = a; i < (int)(b); i++)
#define rep(i,b) range(i,0,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
void fastios(){ ios_base::sync_with_stdio(0); cin.tie(0); }
int const mod = 1000000007;
auto const inf = numeric_limits<int>::max()/8;

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

struct UnionFind {
    vector<int> par;
    int cnt;
    UnionFind(int size_) : par(size_, -1), cnt(size_) { }
    bool merge(int x, int y){
        x = find(x); y = find(y);
        if (x != y) {
            if (par[y] < par[x]) swap(x, y);
            par[x] += par[y]; par[y] = x; cnt--;
        }
        return x != y;
    }
    bool get(int x, int y){ return find(x) == find(y); }
    int find(int x){ return par[x] < 0 ? x : par[x] = find(par[x]); }
    int size(int x){ return -par[find(x)]; }
    int size(){ return cnt; }
};

bool operator < (const Edge &e, const Edge &f){ return e.weight > f.weight; }
pair<Weight, Edges> kruskal(Graph const& g){
    UnionFind uf(g.size());
    Edges es; rep(i, g.size()) for(auto &e : g[i]) es.emplace_back(e);
    sort(all(es)); reverse(all(es)); // !! INVERSE !!
    Weight total = 0; Edges T;
    for(auto &e : es){
        if(uf.get(e.src,e.dst)) continue;
        T.push_back(e); total += e.weight; uf.merge(e.src,e.dst);
    }
    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 << kruskal(g).first << endl;
}

C++: #define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <climits>
#include <list>
#include <queue>

using namespace std;

static const int INFTY = 2001;

int main() {
	int Dist[101];
	int AdjacenceyList[100][100];
	int AdjacenceyWeightList[100][100];
	int Degree[100];
	int i, j;
	int N;
	int W;
	int Deg;
	int MinTotalWeight = 0;
	int u, v;
	int PrevSecondSmallestVertex;
	int SecondSmallestVertex;
	int MinVertex;
	bool inT[100];

	cin >> N;

	for (i = 0; i < N; i++) {
		inT[i] = false;
		Dist[i] = INFTY;
		Deg = -1;
		for (j = 0; j < N; j++) {
			cin >> W;
			if(W != -1){
				AdjacenceyList[i][++Deg] = j;
				AdjacenceyWeightList[i][Deg] = W;
			}
		}
		Degree[i] = Deg + 1;
	}
	Dist[100] = INFTY;

	u = 0;
	inT[u] = true;
	Dist[u] = 0;
	PrevSecondSmallestVertex = 100;
	for (i = 1; i <= N - 1; i++) {
		MinVertex = 100;
		for (j = 0; j < Degree[u]; j++) {
			v = AdjacenceyList[u][j];
			if (inT[v] == false) {
				W = AdjacenceyWeightList[u][j];
				if (W < Dist[v]) {
					Dist[v] = W;
				}
				if (Dist[v] < Dist[MinVertex]) {
					SecondSmallestVertex = MinVertex;
					MinVertex = v;
				}
				else if (Dist[v] < Dist[SecondSmallestVertex]) {
					SecondSmallestVertex = v;
				}
			}
		}

		////DEBUG
		//cout << "MinVerTex = " << MinVertex << " SecondSmallestVertex = " << SecondSmallestVertex << endl;

		if (Dist[PrevSecondSmallestVertex] < Dist[MinVertex]) {
			SecondSmallestVertex = MinVertex;
			MinVertex = PrevSecondSmallestVertex;
			PrevSecondSmallestVertex = SecondSmallestVertex;
		}
		else if (Dist[SecondSmallestVertex] < Dist[PrevSecondSmallestVertex]) {
			PrevSecondSmallestVertex = SecondSmallestVertex;
		}
		inT[MinVertex] = true;
		u = MinVertex;
		MinTotalWeight += Dist[MinVertex];

		////DEBUG
		//cout << "MinVertex = " << MinVertex << " PrevSecondSmallestVertex = " << PrevSecondSmallestVertex << endl;
		//cout << "inT: ";
		//for (int k = 0; k < N; k++) {
		//	cout << inT[k] << " ";
		//}
		//cout << endl;
		//printf("MinTotalWeight = %d\n", MinTotalWeight);
	}
	printf("%d\n", MinTotalWeight);

	return 0;
}