Go: package main

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

const (
	MAX   = 100
	INFTY = 1 << 21
	NIL   = -1
)

const (
	WHITE = iota
	GRAY
	BLACK
)

type Graph [MAX][MAX]int

func (g *Graph) prim(n int) int {
	var (
		u, minv     = 0, 0
		d, p, color [MAX]int
	)

	for i := 0; i < n; i++ {
		d[i] = INFTY
		p[i] = -1
		color[i] = WHITE
	}
	d[0] = 0

	for {
		minv = INFTY
		u = -1
		for 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 v := 0; v < n; v++ {
			if color[v] != BLACK && g[u][v] != INFTY {
				if d[v] > g[u][v] {
					d[v] = g[u][v]
					p[v] = u
					color[v] = GRAY
				}
			}
		}
	}

	sum := 0
	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += g[i][p[i]]
		}
	}

	return sum
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	var g Graph
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			sc.Scan()
			e, _ := strconv.Atoi(sc.Text())
			if e == -1 {
				g[i][j] = INFTY
				continue
			}
			g[i][j] = e
		}
	}

	return fmt.Sprint(g.prim(n))
}

func main() {
	fmt.Println(answer(os.Stdin))
}

C++: #include <iostream>

const int MAX   = 100;
const int INFTY = (1<<21);
const int WHITE = 0;
const int GRAY  = 1;
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) {
        minv = INFTY;
        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] != INFTY) {
                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() {
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int e;
            std::cin >> e;
            M[i][j] = (e == -1) ? INFTY : e;
        }
    }

    std::cout << prim() << std::endl;

    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include<string>
#include <set>
#include <map>
#include <queue>
#include <limits.h>
#include <cmath>

using namespace std;

#define rip(i,n,s) for (int i=(s);i<(int)(n);i++)
#define all(a) (a).begin(),(a).end()
typedef long long ll;

struct UnionFind{
    int size;
    vector<int> par;
    vector<int> rank;
    UnionFind(int x){
        size=x;
        par=vector<int> (x);
        rank=vector<int> (x,1);
        for (int i=0;i<x;i++){
            par[i]=i;
        }
    }
    int root(int x){
        if(par[x]==x){
            return x;
        }
        else{
            return par[x]=root(par[x]);
        }
    }
    void unite(int x,int y){
        x=root(x);y=root(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 check(int x,int y){
        return root(x)==root(y);
    }
    void initialize(){
        for (int i=0;i<size;i++){
            par[i]=i;
        }
    }
};

typedef pair<int,pair<int,int>> P;

int main(){
    int n;
    cin >> n;
    UnionFind uf(n);
    priority_queue<P,vector<P>,greater<P>> q;
    int v;
    P now;
    rip(i,n,0){
        rip(j,n,0){
            cin >> v;
            if(v>=0 && i>j){
                now.first=v;
                now.second.first=i;
                now.second.second=j;
                q.push(now);
            }
        }
    }
    int co=n-1;
    int ans=0;
    while (co){
        now=q.top();
        q.pop();
        if(uf.check(now.second.first,now.second.second)){
            continue;
        }
        ans+=now.first;
        uf.unite(now.second.first,now.second.second);
        co--;
    }
    printf("%d\n",ans);
}

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

static const int MAX = 100;
static const int INF = (1<<30);
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,ii,vv;
  int d[MAX],p[MAX],color[MAX];

  //cout << "prim" << endl;
  //条件初期化
  for(ii=0;ii<n;ii++){
    d[ii] = INF;
    p[ii] = -1;
    color[ii] = WHITE;
  }

  d[0] = 0;

  while(1){

    minv = INF;
    u = -1;

    //起点の決定
    for(ii=0;ii<n;ii++){
      if(minv > d[ii] && color[ii] != BLACK){
        //cout << "ii:" << ii << endl;
        u = ii;
        minv = d[ii];
      }
    }

    if(u == -1){
      break;
    }

    //起点を探索済みに
    color[u] = BLACK;

    for(vv=0;vv<n;vv++){
      //未探索かつパスの繋っている位置
      if(color[vv] != BLACK && M[u][vv] != INF){
        if( d[vv] > M[u][vv]){
          d[vv] = M[u][vv];
          p[vv] = u;
          color[vv] = GRAY;
        }
      }
    }
  }

  int sum = 0;
  for(ii=0;ii<n;ii++){
    if(p[ii] != -1){
      sum += M[ii][p[ii]];
    }
  }
  
  return sum;
  
}

int main(){
  cin >> n;
  int ii,jj;

  for(ii=0;ii<n;ii++){
    for(jj=0;jj<n;jj++){
      int cost;
      cin >> cost;

      if(cost == -1){
        M[ii][jj] = INF;
      }
      else{
        M[ii][jj] = cost;
      }
    }
  }

  cout << prim() << endl;
  
}

C++: #include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
#define FOR(i,a,b)   for(ll i = (a); i < (b); i++ )
#define REP(i, n)    FOR(i,0,n)
typedef pair< int, int >   cp2;
typedef pair< int, cp2 >   cp3;
#define fi first
#define se second
#define sec  se.fi
#define thr  se.se
const ll mod = 1000000007;
//              123456789


 

///////////////////////////////////////////////
//
//
///////////////////////////////////////////////

////////////////////////////////////////////////
////////////////////////////////////////////////



priority_queue< cp3, vector<cp3>, greater<cp3> >p;
cp3 now;

int g[112];

int find( int key ){
	//cout<<key<<" "<<g[key]<<endl;
	if( g[key] < 0 ) return key;
	return g[key] = find( g[key] );
}

void unite( int x, int y ){
	x = find( x );
	y = find( y );
	if( x == y ) return;
	
	if( g[x] < g[y] ) swap( x, y );
	if( g[x] == g[y] ) g[y]--;//??±??????x???????????????
	//g[y] += g[x];		 //????????°???x??????????°???????
	g[x] = y;
}

int a[112][112];
int N;
int ans = 0;

int main(){
	
	cin>>N;
	
	fill( g, g+112, -1 );
	
	
	REP( i, N ){
		REP( j, N ){
			scanf("%d",&a[i][j]);
			if( a[i][j] != -1 ){
				p.push( cp3( a[i][j], cp2(i, j) ) );
				//printf("%d %d %d\n",p[idx].fi, p[idx].sec, p[idx].thr);
				
			}
		}
	}
	
	while( !p.empty() ){
		now = p.top();
		p.pop();
		
		if( find(now.sec) != find(now.thr) ){
			unite( now.sec, now.thr );
			ans += now.fi;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;

}