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 <iostream>
using namespace std;
static const int MAX = 100;
static const int INFINITY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int M[MAX][MAX];
int n;

int prim(){
    int u, minv;
    int d[MAX], p[MAX], color[MAX];

    for(int i = 0; i < n; i ++){
        d[i] = INFINITY;
        p[i] = -1;
        color[i] = WHITE;
    }

    d[0] = 0;

    while(1){

        // for(int i = 0; i < n; i++){ //for check
        //     printf("%d ", d[i]);
        // }

        // printf("\n");

        minv = INFINITY;
        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] != INFINITY){
                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(void){
    cin >> n;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            int e;
            cin >> e;
            if (e != -1){ 
                M[i][j] = e;
            }else{
                M[i][j] = INFINITY; //無限大を挿入
            }
        }
    }

    cout << prim() << endl;

    return 0;

}

/*
5
-1 2 3 1 -1
2 -1 -1 4 -1
3 -1 -1 1 1
1 4 1 -1 3
-1 -1 1 3 -1
 */

C++: #include<iostream>
#include<queue>
#include<map>
using namespace std;
typedef pair< int, int > Pi;
int info[100][100];
bool used[100];

int prim(const int& V) {
    priority_queue< Pi > que;
    que.push(Pi());
    int ret = 0;
    while (!que.empty()) {
        Pi p = que.top(); que.pop();
        if (!~- p.first || used[p.second]++) continue;
        ret -= p.first;
        for (int i = 0; i < V; i++) que.push(Pi(-info[p.second][i], i));
    }
    return ret;
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> info[i][j];
        }
    }
    cout << prim(N) << endl;
}

C++: //kruskal tree
#include <iostream>
#include <algorithm>
using namespace std;
#define M 9999
int parent[M],a[M],b[M];
pair<int,int>node[M];
int root(int a){return parent[a]==a?a:parent[a]=root(parent[a]);}
int unite(int a,int b){
	int x=root(a),y=root(b);
	if(x==y)return 0;
	parent[x]=y;
	return 1;
}
int main(){
	int i,j,s,n,m,x;
	cin>>n;
	for(m=i=0;i<n;i++)for(j=0;j<n;j++)if(cin>>x,~x)a[m]=i,b[m]=j,node[m].first=x,node[m].second=m++;
	sort(node,node+m);
	for(i=0;i<n;i++)parent[i]=i;
	for(s=i=0;i<m;i++)if(unite(a[node[i].second],b[node[i].second]))s+=node[i].first;
	cout<<s<<endl;
}

C++: #define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
//#include "MyMath.h"
//#include "MyDisjointset.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <stdio.h>
using namespace std;
typedef pair<int, int> P;
const int INF = 2000000000;
int main() {
	int n; cin >> n;
	int m[101][101];
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)
		cin >> m[i][j];
	int res = 0;
	int *d = new int[n];
	fill(d, d + n, INF); 
	d[0] = 0;
	bool *visit = new bool [n];
	priority_queue <P, vector<P>, greater<P> > q;
	q.push(P(d[0], 0));
	while (!q.empty()) {
		int f = q.top().first, s = q.top().second;
		visit[s] = true;
		res += f;
		q.pop();
		for (int i = 0; i < n; i++)
			if (!visit[i] && m[s][i] != -1 && m[s][i] > d[i]) {
				d[i] = m[s][i];
				q.push(P(d[i], i));
			}
	}
	cout << res << endl;
	delete[] d, visit;
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

template<typename T>
struct Kruskal{
    struct edge{
        int from,to,used; T cost;
        edge(int from,int to,T cost):
            from(from),to(to),cost(cost),used(0){}
        bool operator<(const edge &e) const{
            if (cost!=e.cost) return cost<e.cost;
            else if (from!=e.from) return from<e.from;
            else return to<e.to;
        }
    };
    int num;
    vector<int> par,rank;
    vector<edge> es;
    Kruskal(int n):num(n),par(n),rank(n,1){
        iota(par.begin(),par.end(),0);
    }
    int root(int x){
        if (par[x]==x) return x;
        return par[x]=root(par[x]);
    }
    bool merge(int x, int y){
        x=root(x),y=root(y);
        if (x==y) return false;
        if (rank[x]<rank[y]) swap(x,y);
        par[y]=x;
        rank[x]+=rank[y];
        --num;
        return true;
    }
    bool same(int x, int y){return root(x)==root(y);}
    int size(int x){return rank[root(x)];}
    int count(){return num;}
    void add_edge(int u,int v,T c){
        es.emplace_back(u,v,c);
    }
    T build(){
        sort(es.begin(),es.end());
        T res=0;
        for (auto &e:es){
            if (!same(e.from,e.to)){
                res+=e.cost;
                merge(e.from,e.to);
                e.used=1;
            }
        }
        return res;
    }
    vector<int> used_es(T &c){
        int E=es.size();
        map<edge,int> m;
        for (int i=0;i<E;++i) m[es[i]]=i;
        c=build();
        vector<int> list(E);
        for (int i=0;i<E;++i) list[m[es[i]]]=es[i].used;
        return list;
    }
};

// https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_12_A

void ALDS1_12_A(){
    int n; cin >> n;
    Kruskal<int> K(n);
    vector<vector<int>> a(n,vector<int>(n));
    for (int i=0;i<n;++i){
        for (int j=0;j<n;++j){
            cin >> a[i][j];
            if (j>i&&~a[i][j]) K.add_edge(i,j,a[i][j]);
        }
    }
    cout << K.build() << '\n';
}

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