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

int n;					//えぬ
int a[100][100] = {0};	//辺の重さ
int f[100] = {0};		//その頂点がすでに連結済みかどうか、その集団の番号
int c = 0;				//全体の重さ
int d = 1;				//次につける集団番号
int s = 0;				//選んだ本数
vector<int> w;			//木のリスト、軽いもの順
int wc = 0;				//見てる木のリストの位置

int main(){
	cin >> n;
	//まず辺の重さをaに入れる
	//wに辺のリストを入れる
	for ( int i = 0; i < n; i++ ) {
		for ( int j = 0; j < n; j++ ) {
			cin >> a[i][j];
			if ( a[i][j] != -1 && i < j ) w.push_back( a[i][j] );
		}
	}
	sort( w.begin(),w.end() );
	while(true) {									//n-1本選ぶまで無限ループ
		for ( int i = 0; i < n - 1; i++ ) {			// i < j を満たすように木を調べ続ける
			for ( int j = i + 1; j < n; j++ ) {
				if ( a[i][j] != w[wc] ) continue;	//その木が一番軽い木だったらそれを対象に検査を始める
				if ( f[i] > 0 && f[j] > 0 ) {		//その木の両端が両方とも連結済みだったら
					if ( f[i] != f[j] ) {
						int y = f[j];
						for ( int x = 0; x < n; x++ ) {
							if ( f[x] == y ) f[x] = f[i];
						}
						c += a[i][j];
						s++;
					}
				}else if ( f[i] == 0 && f[j] == 0 ) {
					f[i] = d;
					f[j] = d;
					d++;
					c += a[i][j];
					s++;
				}else {
					if ( f[i] == 0 ) {
						f[i] = f[j];
						c += a[i][j];
						s++;
					}else {
						f[j] = f[i];
						c += a[i][j];
						s++;
					}
				}
				wc++;
				a[i][j] = -1;
				if ( s == n-1 ) break;
			}
			if ( s == n-1 ) break;
		}
		if ( s == n-1 ) break;
	}
	cout << c << endl;
	return 0;
}

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

using namespace std;

#define Vi vector<int>
#define FOR(i,s,e) for (int i=s; i<e; i++)
#define ITER(v) v.begin(), v.end()

constexpr int N_MAX = 100;

int weight[N_MAX][N_MAX];

int mst(const int n) {
    bool ismember[n] = {false};
    Vi members;

    members.push_back(0);
    ismember[0] = true;
    int cost = 0;

    FOR(t,1,n) {
        int addcost = -1;
        int newmember = -1;
        for (const int i : members)
        FOR(j,0,n) {
            if (ismember[j]) { continue; }
            const int w = weight[i][j];
            if (w < 0) { continue; }
            if (addcost < 0 || addcost > w) {
                addcost = w;
                newmember = j;
            }
        }
        members.push_back(newmember);
        ismember[newmember] = true;
        cost += addcost;
        //cout << "#" << newmember << endl;
    }
    return cost;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    FOR(i,0,n) {
        FOR(j,0,n) {
            cin >> weight[i][j];
        }
    }

    int cost = mst(n);
    cout << cost << endl;

    return 0;
}

C++: #include<iostream>
using namespace std;
#define INFTY (1 << 30)

enum Color {
	WHITE,
	GRAY,
	BLACK,
};

void Prim(int verValWeight[][100], int verNum) {
	int distance[100];
	Color color[100];
	int parent[100];
	for (int i = 0; i < verNum; i++) {
		color[i] = WHITE;
		distance[i] = INFTY;
		parent[i] = -1;
	}
	distance[0] = 0;

	while (true) {
		int min_cost = INFTY;
		int subScript;
		for (int i = 0; i < verNum; i++) {
			if (color[i] != BLACK && distance[i] < min_cost) {
				min_cost = distance[i];
				subScript = i;
			}

			if (min_cost == INFTY)
				break; //end

			color[subScript] = BLACK;

			for (int i = 0; i < verNum; i++) {
				if (color[i] != BLACK && verValWeight[subScript][i] != INFTY) {
					if (verValWeight[subScript][i] < distance[i]) {
						distance[i] = verValWeight[subScript][i];
						parent[i] = subScript;
						color[i] = GRAY;
					}
				}
			}
		}
	}

	int weight_sum = 0;
	for (int i = 0; i < verNum; i++)
		if (parent[i] != -1)
			weight_sum += verValWeight[i][parent[i]];
	cout << weight_sum << endl;

}

int main() {
	int verNum;
	int verValWeight[100][100];
	int parent[100];

	cin >> verNum;
	for (int i = 0; i < verNum; i++)
		for (int j = 0; j < verNum; j++) {
			cin >> verValWeight[i][j];
			if (verValWeight[i][j] == -1) verValWeight[i][j] = INFTY;
		}

	Prim(verValWeight, verNum);

	return 0;
}

C++: #include <iostream>
//#include <string>
#include <algorithm>
using namespace std;
//#define int long long
//#define _DEBUG
class UnionFindTree{
    private:
    int P[10010];
    public:
    UnionFindTree(int N){
        for(int i=0; i<=N; i++) P[i] = i;
    }
    int root(int a){
        if (P[a] == a) return a;
        return (P[a] = root(P[a]));
    }
    bool is_same_set(int a, int b){
        return root(a) == root (b);
    }
    void unite(int a, int b){
        P[root(a)] = root(b);
    }
};
struct weight_edge{// (weight, (vert_a,vert_b))
    int w;
    int a;
    int b;
};
int n, k;
weight_edge we[10007];
bool com_we(weight_edge a, weight_edge b){
    return ((a.w == b.w)? a.a < b.a: a.w < b.w);
}
int solve(){
    if(n==0)return 0;
    sort(we, we+k, com_we);
    //for(int i=0; i<k; i++)printf("%d,%d,%d\n",we[i].w,we[i].a,we[i].b);
    auto uft = UnionFindTree(n);
    int i=0, r=0, l=0;
    while(l<n-1){
        if(!uft.is_same_set(we[i].a, we[i].b)){
            uft.unite(we[i].a, we[i].b);
            r += we[i].w;
            l++;
            //printf("%d;\tw:%d,\t(%d,%d)\n",l,we[i].w,we[i].a,we[i].b);
        }
        i++;
    }
    return r;
}
void get(){
    k = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int t;
            cin >> t;
            if(i<j && t>=0){
                we[k].w = t;
                we[k].a = i; we[k].b = j;
                k++;
            }
            //cout << t<<":"<<i<<","<<j<<"\t";
        }
        //cout << endl;
    }
    //cout << "k"<<k<<endl;
}
signed main(){    
    while(cin >> n){
        get();
        cout << solve() <<  endl;
    }
}