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>
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 100;
const int AMAX = 2001;
int A[NMAX][NMAX];
int C[NMAX];
int n;

int MST(int a) {
	C[a] = 1;
	int sum, minv, mina;
	sum = 0;

	while (true) {
		minv = AMAX;
		mina = -1;
		for (int i = 0; i < n; i++) {
			if (C[i] == 0) {
				continue;
			}
			for (int j = 0; j < n; j++) {
				if (C[j] == 1 || A[i][j] == AMAX) {
					continue;
				}
				minv = min(A[i][j], minv);
				if (A[i][j] == minv) {
					mina = j;
				}
			}
		}
		if (minv == AMAX || mina == -1) {
			break;
		}
		C[mina] = 1;
		sum += minv;
	}

	return sum;
}

int main() {
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		C[i] = 0;
		for (int j = 0; j < n; j++) {
			scanf("%d", &A[i][j]);
			if (A[i][j] == -1) {
				A[i][j] = AMAX;
			}
		}
	}

	printf("%d\n", MST(0));

	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define REP(i,n) for(auto i = 0 * n; i < (n); ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,e) for (ll i = s; i < (ll)e; i++)
#define TEN(x) ((ll)1e##x)

class UnionFind {
	typedef size_t U;
	vector<int32_t> v;
public:
	UnionFind(U n) : v(n, -1) {}
	U find(U x) { return v[x] < 0 ? x : (v[x] = find((U)v[x])); }
	bool same(U x, U y) { return find(x) == find(y); }
	U size(U x) { return (U)-v[find(x)]; }
	void unite(U x, U y) {
		x = find(x); y = find(y);
		if (x != y) {
			if (-v[x] < -v[y]) swap(x, y);
			v[x] += v[y];
			v[y] = x;
		}
	}
};

struct Edge{ uint32_t to, id; };
typedef vector<vector<Edge>> Graph;

template<class T> struct Kruskal{
	typedef uint32_t U;
	template<class V> Kruskal(U n, const V & u, const V & v, const vector<T> & w) : g(n) {
		vector<U> es(w.size());
		iota(es.begin(), es.end(), 0);
		sort(es.begin(), es.end(), [&](U i, U j) { return w[i] < w[j]; });
		UnionFind uf(n);
		for (U i : es) {
			if (!uf.same(u[i], v[i])) {
				uf.unite(u[i], v[i]); cost += w[i];
				g[u[i]].push_back({v[i], i}); g[v[i]].push_back({u[i], i});
			}
		}
	}
	Graph g; T cost = 0;
};

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);

	ll n; cin >> n;
	vl u, v, w;
	REP(i, n) REP(j, n) {
		ll x; cin >> x;
		if (x != -1) {
			u.push_back(i);
			v.push_back(j);
			w.push_back(x);
		}
	}
	Kruskal<ll> mst(n, u, v, w);
	cout << mst.cost << endl;
}

C++: #include<bits/stdc++.h>
using namespace std;
static const int Maxn = 110;
static const int INFTY = (1 << 21);
static const int WHITE = 0;
static const int BLACK = 1;

int n, a[Maxn][Maxn], color[Maxn], p[Maxn], d[Maxn];

int prim(){
	for(int i = 0; i < n; i++){
		d[i] = INFTY; p[i] = -1;
	}
	d[0] = 0;
	while(1){
		int minv = INFTY, u = -1;
		for(int i = 0; i < n; i++){
			if(d[i] < minv && color[i] != BLACK){
				minv = d[i];
				u = i;
			}
		}
		if(u == -1) break;
		color[u] = BLACK;
		for(int i = 0; i < n; i++){
			if(a[u][i] < d[i] && color[i] != BLACK){
				d[i] = a[u][i];
				p[i] = u;
			}
		}
	}
	int sum = 0;
	for(int i = 1; i < n; i++) sum += a[i][p[i]];
	return sum;
}
int main()
{
	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> a[i][j];
			a[i][j] = (a[i][j] == -1) ? INFTY : a[i][j];  
		} 
	}
	cout << prim() << endl;
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=105,INF=1<<30;
int state[MAX],N,S[MAX][MAX];
priority_queue<pair<int,int>> Q;

int prim(){
    int sum=0,cnt=1;
    for(int i=0;i<N;i++){
        state[i]=0;
    }
    state[0]=1;
    for(int i=0;i<N;i++){
        if(S[0][i]!=INF) Q.push(make_pair(-S[0][i],i));
    }
    while(1){
        int a=Q.top().first;
        int b=Q.top().second;
        Q.pop();
        if(state[b]==0){
            sum+=-a;
            state[b]=1;
            cnt++;
            for(int i=0;i<N;i++){
                if(S[b][i]!=INF&&state[i]==0) Q.push(make_pair(-S[b][i],i));
            }
        }
        if(cnt==N) break;
    }
    return sum;
}



int main(){
    
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int a;cin>>a;
            if(a==-1) S[i][j]=INF;
            else S[i][j]=a;
        }
    }
    cout<<prim()<<endl;

}

C++: #include <iostream>
using namespace std;

int n;
int a[101][101];
int flg[101];
int t[101];
int sum = 0;

void visit(){
  int ima = 0;
  int mine = 100000000;
  
  
  for(int k=0;k<n-1;k++) {
    mine = 10000000;
    for(int i=0;i<n;i++) {
      if(flg[i] == 0 && mine > t[i]) {
	mine = t[i];
	ima = i;
      }
    }
    sum += mine;
    flg[ima] = 1;
    
    for(int i=0;i<n;i++) 
      if(a[ima][i] != -1) 
	if(t[i] > a[ima][i] ) t[i] = a[ima][i];
    
    
  }
}

int main() {

  cin >> n;

  for(int i=0;i<n;i++) 
    for(int j=0;j<n;j++) 
      cin >> a[i][j];
  
  for(int i=0;i<n;i++) {
    flg[i] = 0;
    t[i] = 100000000;
  }
  
  t[0] = 0;
  flg[0] = 1;
  for(int i=0;i<n;i++) 
    if(a[0][i] != -1) t[i] = a[0][i];

  visit();

  cout << sum << endl;
 
  return 0; 
  
}

C++: #include<iostream>
#include<cstdio>
using namespace std;

int n, M[100][100];

int prim()
{
	int i,u,v,min_v,sum;
	int d[100],p[100],c[100];
	
	for(i=0;i<=n-1;i++)
	{
		d[i]=(1<<21);
		p[i]=-1;
		c[i]=0;
	}
	
	d[0]=0;
	
	while(1)
	{
		min_v=(1<<21);
		u=-1;
		for(i=0;i<=n-1;i++)
		{
			if(min_v > d[i] && c[i] != 2)
			{
				u=i;
				min_v=d[i];
			}
		}
		if(u==-1) break;
		c[u]=2;
		for(v=0;v<=n-1;v++)
		{
			if(c[v] != 2 && M[u][v] != (1<<21))
			{
				if(d[v] > M[u][v])
				{
				    d[v]=M[u][v];
				    p[v]=u;
				    c[v]=1;
				}
			}
		}
	}
	sum=0;
	for(i=0;i<=n-1;i++)
	{
		if(p[i] != -1) sum+=M[i][p[i]];
	}
	return sum;
}

int main()
{
	int i,j,e;
	cin >> n;
	
	for(i=0;i<=n-1;i++)
	{
		for(j=0;j<=n-1;j++)
		{
			cin >> e;
			if(e == -1) M[i][j]=(1<<21);
			else M[i][j]=e;
		}
	}
	
	cout << prim() << endl;
	return 0;
}