Go: package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)

const (
	white int = iota
	gray
	black
)
const INFTY int = 2001

var G [][]int
var color []int
var d []int
var p []int
var N int

func prim() int {
	u := 0
	d[u] = 0
	for {
		minCost := INFTY
		for i:=0; i<N; i++ {
			if color[i] != black && d[i] < minCost {
				minCost = d[i]
				u = i
			}
		}

		if minCost == INFTY {
			break
		}

		color[u] = black

		for v:=0; v<N; v++ {
			if color[v] != black && G[u][v] != -1 {
				if G[u][v] < d[v] {
					d[v] = G[u][v]
					p[v] = u
					color[v] = gray
				}
			}
		}
	}
	// sum
	sum := 0
	for i:=0; i<N; i++ {
		if p[i] != -1 {
			sum += G[i][p[i]]
		}
	}
	return sum
}




func initVariable(N int) {
	G = make([][]int, N)
	for i:=0; i<N; i++ {
		G[i] = make([]int, N)
	}
	color = make([]int, N)
	d = make([]int, N)
	p = make([]int, N)
	for i:=0; i<N; i++ {
		d[i] = INFTY
		p[i] = -1
	}
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	N = nextInt(scanner)
	initVariable(N)
	for i:=0; i<N; i++ {
		for j:=0; j<N; j++ {
			G[i][j] = nextInt(scanner)
		}
	}
	fmt.Printf("%d\n", prim())
}

C++: # include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

int V;
int E;
struct edge { int from, to, cost; };

typedef pair<int, int> PP;

vector<edge> e;

int Par[100000];
int Rank[100000];

void init(int n) {
	for (int i = 0; i < n; i++) {
		Par[i] = i;
		Rank[i] = 0;
	}
}

int find(int x) {
	if (Par[x] == x) {
		return x;
	}
	else {
		return Par[x] = find(Par[x]);
	}
}

void unite(int  x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (Rank[x] < Rank[y]) {
		Par[x] = y;
	}
	else {
		Par[y] = x;
		if (Rank[x] == Rank[y])Rank[x]++;
	}
}

bool same(int x, int y) {
	return find(x) == find(y);
}

// ソート時に比較するための関数 
bool comp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}

int kruskal() {
	init(V);
	sort(e.begin(), e.end(), comp);
	int ans = 0;
	for (int i = 0; i<E; i++) {
		if (!same(e[i].from, e[i].to)) {
			unite(e[i].from, e[i].to);
			ans += e[i].cost;
		}
	}
	return ans;
}

int main() {
	cin >> V;
	REP(i, V)REP(j, V) {
		int num;
		cin >> num;
		e.emplace_back(edge{(int)i, (int)j, num});
		E++;
	}
	cout << kruskal() << endl;
}

C++: #include <iostream>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

static const int MAX = 100;

struct node{int key, fi, fj;
        bool operator<(const node& rhs)const
    {
        return key > rhs.key;
    }
};

int n;
int A[MAX][MAX];
priority_queue<node> p_q;
int check[MAX];

int main(int argc, const char * argv[]) {
    // input from txt
    
    /////////
    //write//
    /////////
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> A[i][j];
            if(A[i][j] != -1){
                p_q.push({A[i][j], i, j});
            }
        }
    }
    fill(check, check+n, 0);
    
    
    int cnt = 0;
    int ans = 0;
    int now_id = 1;
    while(!p_q.empty()){
        int fi = p_q.top().fi;
        int fj = p_q.top().fj;
        int key = p_q.top().key;
        p_q.pop();
        
        if(!check[fi] && !check[fj]){
            check[fi] = now_id;
            check[fj] = now_id;
            ans+=key;
        }
        else if(!check[fi]){
            cnt = 0;
            int a = check[fj];
            for(int i=0; i<n; i++){
                if(check[i] == a){
                    check[i] = now_id;
                    cnt++;
                }
            }
            check[fi] = now_id;
            cnt++;
            ans+=key;
        }
        else if(!check[fj]){
            cnt = 0;
            int a = check[fi];
            for(int i=0; i<n; i++){
                if(check[i] == a){check[i] = now_id;
                cnt++;
                }
            }
            check[fj] = now_id;
            cnt++;
            ans+=key;
        }
        else if(check[fi] != check[fj]){
            int a = check[fj];
            int b = check[fi];
            cnt = 0;
            for(int i=0; i<n; i++){
                if(check[i] == a){
                    check[i] = now_id;
                    cnt++;
                }
            
            }
            for(int i=0; i<n; i++){
                if(check[i] == b){
                    check[i] = now_id;
                    cnt++;
                }
            }
            ans+=key;
        }
        if(cnt>=n)break;
        now_id++;
    }
    
    cout << ans << endl;
    
    return 0;
}

C++: #include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

typedef long long signed int ll;

constexpr ll NIL = -20000000000;

int n,z[100][100];
set <int> t;

int main() {
    cin >> n;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> z[i][j];
            if(z[i][j] == -1) z[i][j] = 100000;
        }
    }
    int res = 0;
    t.insert(0);
    while(t.size() != n) {
        int me = 100000;int mi = -1;
        for(auto e:t) {
            for(int i = 0;i < n;i++) {
                if(me > z[e][i] && t.find(i) == t.end()) {
                    me = z[e][i];
                    mi = i;
                }
            }
        }
        res += me;
        t.insert(mi);
    }
    cout << res << endl;
}

C++: #include<stdio.h>
using namespace std;
const int sss=1<<21;
int n;
int a[1000][1000];
int d[1000],p[10000],color[1000];
int prim(){
    int u,minv;
    for(int i=0;i<n;i++){
        d[i]=sss;
        p[i]=-1;
    }
    d[0]=0;
    while(1){
        minv=sss;
        u=-1;
        for(int i=0;i<n;i++){
            if(minv>d[i]&&color[i]!=1){
                u=i;
                minv=d[i];
            }
        }
        if(u==-1) break;
        color[u]=1;
        for(int v=0;v<n;v++){
            if(color[v]!=1&&a[u][v]!=sss){
                if(d[v]>a[u][v]){
                    d[v]=a[u][v];
                    p[v]=u;
                }
            }
        }
    }
    int sum=0;
    for(int i=0;i<n;i++){
        if(p[i]!=-1) {
            sum+=a[p[i]][i];
        }
    }
    return sum;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int e;scanf("%d",&e);
            a[i][j]=e==-1?sss:e;
        }
    }
    printf("%d\n",prim());
    return 0;
}