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++: #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]];
            
        }
        
    }
    
    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 <iostream>
#include <utility>
#include <algorithm>
using namespace std;

int m,n,x,ans;
int P[100+10],edge1[10000+10],edge2[10000+10];


int root(int a){
	if (P[a] == a) return a;
	return (P[a] = root(P[a]));
}

bool same(int a, int b){
	return root(a)==root(b);
}
	
void unite(int a, int b){
	P[root(a)] = root(b);
}

int main() {
	pair<int,int> edges[10000+10];
	cin >> n;
	
	for (int i=1; i<=n; i++){
		P[i] = i;
	}
	
	m = 0;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			cin >> x;
			if (x>-1){
				edge1[m] = i;
				edge2[m] = j;
				edges[m] = make_pair(x, m);
				m+=1;
			}
		}
	}
	
	sort(edges, edges+m);
	n=1;
	for (int i=0; i<m; i++){
		if (n>=m) break;
		if (!same(edge1[edges[i].second], edge2[edges[i].second])){
			unite(edge1[edges[i].second], edge2[edges[i].second]);
			ans += edges[i].first;
			n+=1;
		}
	}
	
	cout << ans << endl;
	
}

C++: #include <bits/stdc++.h>

using namespace std;
using LL = long long;
using P = pair<int, int>;
using Tapris = tuple<int, int, int>;

#define REP(i, n) for(LL i = 0; i < n; ++i)
#define FOR(i, a, n) for(LL i = a; i < n; ++i)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e15;
const int MOD = 1e9 + 7;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

//#define int long long

class UnionFind {
    private:
        vector<int> parent;  // 親
        vector<int> rank;    // 木の深さ
    public:
        UnionFind(int n);          // n要素で初期化
        int Find(int x);           // 木の根を返す
        void Unite(int x, int y);  // xとyの属する集合を併合
        bool Same(int x, int y);   // xとyが同じ集合に属するか否か
};

UnionFind::UnionFind(int n) : parent(vector<int>(n)), rank(vector<int>(n)) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

int UnionFind::Find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return parent[x] = Find(parent[x]);
    }
}

void UnionFind::Unite(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;

    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}

bool UnionFind::Same(int x, int y) { return Find(x) == Find(y); }

template <typename T>
struct Edge {
    int src, to;
    T cost;
    Edge(int to, T cost) : src(-1), to(to), cost(cost) {}
    Edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
};

template<typename T>
using Edges = vector<Edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T>>;


template <typename T>
class Kruskal {
    private:
        int V; // 頂点数
        Edges<T> edges;
        WeightedGraph<T> minimumSpanningTree;
    public:
        Kruskal(int n);
        void AddEdge(int from, int to, T cost);
        T Run();
        WeightedGraph<T> GetMinimumSpanningTree();
};

template <typename T>
Kruskal<T>::Kruskal(int n) : V(n), minimumSpanningTree(n) {}

template <typename T>
void Kruskal<T>::AddEdge(int from, int to, T cost) {
    edges.push_back(Edge<T>(from, to, cost));
}

template <typename T>
T Kruskal<T>::Run() {
    sort(edges.begin(), edges.end(), [](const Edge<T> &a, const Edge<T> &b){
        return a.cost < b.cost;
    });
    UnionFind tree(V);
    T total = 0;
    
    for(auto &e : edges){
        if(!tree.Same(e.src, e.to)){
            tree.Unite(e.src, e.to);
            total += e.cost;
            minimumSpanningTree[e.src].push_back(Edge<T>(e.to, e.cost));
            minimumSpanningTree[e.to].push_back(Edge<T>(e.src, e.cost));
        }
    }

    return total;
}

template <typename T>
WeightedGraph<T> Kruskal<T>::GetMinimumSpanningTree(){
    return minimumSpanningTree;
}

/*************** using variables ***************/

/**********************************************/

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    Kruskal<int> kruskal(n);
    REP(i, n){
        REP(j, n){
            int x;
            cin >> x;
            if(x != -1) kruskal.AddEdge(i, j, x);
        }
    }
    int total = kruskal.Run();
    cout << total << endl;
}