Go: package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	I int
	J int
	A int
}

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]int, n)
	edges := make([]Edge, 0, n*(n-1)/2)
	parents := make([]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&g[i][j])
			if g[i][j] >= 0 {
				edges = append(edges, Edge{i, j, g[i][j]})
			}
		}
		parents[i] = i
	}
	sort.SliceStable(edges, func(i, j int) bool { return edges[i].A >= edges[j].A })

	sum := 0
	num := 0
	for len(edges) > 0 && num < n-1 {
		edge := edges[len(edges)-1]
		edges = edges[:len(edges)-1]

		if same(edge.I, edge.J, &parents) {
			continue
		}
		union(edge.I, edge.J, &parents)
		sum += edge.A
		num += 1
	}
	fmt.Println(sum)
}



func root(id int, parents *[]int) int {
	if id == (*parents)[id] {
		return id
	}
	return root((*parents)[id], parents)
}

func union(i, j int, parents *[]int) {
	(*parents)[root(j, parents)] = (*parents)[root(i, parents)]
}

func same(i, j int, parents *[]int) bool {
	return root(i, parents) == root(j, parents)
}

C++: #define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

#define REP(i,n) for(int i=0;(i)<(n);(i)++)
#define ll long long

static const int INFTY = (1 << 25);

int G[100][100], n;

int makeMST() {
	bool mask[100][100];//MAST????????¨???????????¨???????????¨?????????1
	REP(i, n) {
		REP(j, n) mask[i][j] = 0;
	}

	bool color[100];//MST?????\??£??????1
	REP(i, n) color[i] = 0;

	color[0] = 1;//?????????????????¨??????0?????\??????

	REP(k, n - 1) {
		int minv = INFTY;
		int mNodej = -1;
		int mNodei = -1;
		REP(i, n) {
			if (color[i] == 1) {
				REP(j, n) {
					if (G[i][j] != -1) {
						if (color[j] == 0) {
							if (G[i][j] < minv) {
								minv = G[i][j];
								mNodei = i;
								mNodej = j;
							}
						}
					}
				}
			}
		}
		mask[mNodei][mNodej] = 1;
		mask[mNodej][mNodei] = 1;
		color[mNodej] = 1;
	}

	REP(i, n) {
		REP(j, n) {
			if (mask[i][j] == 0) G[i][j] = -1;
		}
	}

	int ans = 0;
	REP(i, n) {
		REP(j, n) {
			if (G[i][j] != -1) ans += G[i][j];
		}
	}

	return ans / 2;
}

int main() {
	cin >> n;

	REP(i, n) {
		REP(j, n) G[i][j] = INFTY;
	}
	REP(i, n) {
		REP(j, n) cin >> G[i][j];
	}

	cout << makeMST() << endl;


	return 0;
}

C++: #include <iostream>
#include <algorithm>
#define N 100
#define INF 2000000000
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;

int n;
int M[N][N],color[N],d[N],p[N];
   //M??????????????????color????¨??????¶???(0,1,2),d????????????????°???????????¨????
   //p???MST???????°???¨?????¨??????????????????????????????

int Prim() {
	for (int i = 0;i < n;i++) d[i] = INF;
	d[0] = 0;  //?????????????????????????????§???????????§????´???????????????????????????????
	/*p[0] = -1;  //?????????????????????????????????????????? (???????????£????????????)*/

	int u;
	while (true) {
		int min = INF;
		for (int i = 0;i < n;i++) {  //MST????§???????????????????????????????????±????
			if(color[i]!=BLACK&&min>d[i]){
				min = d[i];  //??´??°?????????????????°min?????°??????d[i]???????´??????????????????????...
				u = i;
			}
		}

	if (min == INF) break; //????????\?????????d[i]?????´??°??§???????????¨???????????¨

	color[u] = BLACK;

	for (int v = 0;v < n;v++) 
		if(color[v]!=BLACK&&M[u][v]!=-1)
			if (M[u][v] < d[v]) {
				d[v] = M[u][v];  //?????????????????????????±????
				/*p[v] = u;*/
				/*color[v] = GRAY;(????????????bcSSSP??§?????¢?´¢?????????????????????????????§?????????S)*/
			}

	}

	int sum = 0;
	for (int i = 0;i < n;i++) sum += d[i];  //d[i]???????¨????MST???????????????
	return sum;
		
}

int main() {
	cin >> n;
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++) {
			cin >> M[i][j];
			if (M[i][j] == -1) M[i][j] = INF;
		}

	cout<<Prim()<<endl;

}

C++: #define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
const int W = 0;const int G = 1;const int B = 2;
int n; vector<vector<int>>M;
int prim() {
	int u, minv;
	vector<int>d(n, INF), p(n, -1), color(n, W);
	d[0] = 0;
	while (1) {
		minv = INF;
		u = -1;
		rep(i, 0, n) {
			if (minv > d[i] && color[i] != B) {
				minv = d[i];
				u = i;
			}
		}
		if (u == -1)break;
		color[u] = B;
		rep(v, 0, n) {
			if (color[v] != B&&M[u][v] < d[v]) {
				d[v] = M[u][v];
				p[v] = u;
			}
		}
	}
	int sum(0);
	rep(i, 0, n) {
		if (p[i] != -1)sum += M[i][p[i]];
	}
	return accumulate(d.begin(), d.end(),0);

}
signed main() {
	cin >> n; M = vector<vector<int>>(n, vector<int>(n,INF));
	rep(i, 0, n) {
		rep(j, 0, n) {
			int e; cin >> e;
			M[i][j] = (e == -1) ? INF : e;
		}
	}
	cout << prim() << endl;
	return 0;
}

C++: #include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <sstream>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	
	bool added[n];
	int a[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			int buf;
			scanf("%d", &buf);
			a[i][j] = buf==-1 ? INT_MAX : buf;
		}
		added[i] = false;
	}
	added[0] = true;
	
	long total = 0;
	for(;1;){
		bool end = true;
		int minCost = INT_MAX, pi, pj;
		for(int i = 0; i < n; i++){
			if(!added[i]){
				end = false;
				continue;
			}
			for(int j = 0; j < n; j++){
				if(minCost > a[i][j]){
					minCost = a[pi = i][pj = j];
				}
			}
		}
		if(end) break;
		added[pi] = added[pj] = true;
		a[pj][pi] = a[pi][pj] = INT_MAX;
		total += minCost;
	}
	
	printf("%ld", total);
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

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){
        u = -1;
        minv = INFTY;

        //到達可能で最も近いものを探索
        for(int i = 0; i < n; i++){
            if(color[i] != BLACK && d[i] < minv){
                u = i;
                minv = d[i];
            }
        }
        
        //全て到達したらbreak
        if(u == -1) break;

        //1接点を確定
        color[u] = BLACK;

        //到達可能な接点との距離を更新
        for(int v = 0; v < n; v++){
            if(color[v] != BLACK && M[u][v] != INFTY){
                if(M[u][v] < d[v]){
                    d[v] = M[u][v];
                    color[v] = GRAY; //この行はなくても機能しそう
                    p[v] = u;
                }
            }
        }

    }
    //MSTのコストを計算
    int sum = 0; 
    for(int v = 0; v < n; v++){
        if(p[v] != -1) sum += M[p[v]][v];
    }
    return sum;
}

int main(){
    cin >> n;

    rep(i,n)rep(j,n){
        int e;
        cin >> e;
        M[i][j] = (e == -1) ? INFTY : e;
    }

    cout << prim() << endl;
    
    return 0;
}