Go: package main

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

//util
var sc = bufio.NewScanner(os.Stdin)

func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func printList(list []int) {
	n := len(list)
	buf := bufio.NewWriter(os.Stdout)
	for _, v := range list[0 : n-1] {
		buf.Write([]byte(fmt.Sprintf("%d ", v)))
	}
	buf.Write([]byte(fmt.Sprintf("%d\n", list[n-1])))
	buf.Flush()
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

//solve
const (
	MAX   = 100
	INFTY = (1 << 21)
	WHITE = 0
	GRAY  = 1
	BLACK = 2
)

//V: グラフの頂点全体の集合
//T: MSTに属する頂点の集合
var (
	n     int
	M     [MAX][MAX]int //重みを記録する隣接行列
	color [MAX]int
	p     [MAX]int //MSTにおける頂点の親を記録
	d     [MAX]int //Tに属する頂点と、V−Tに属する頂点を繋ぐ辺の中で、重みが最小のものを記録
)

func prim() int {
	var u, minv int
	//初期化
	for i := 0; i < n; i++ {
		d[i] = INFTY
		p[i] = -1
		color[i] = WHITE
	}

	d[0] = 0

	for {
		//頂点uを決めていく
		//つまり、Tに属する頂点と、V−Tに属する頂点を繋ぐ辺の中で、重みが最小のものを決める
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			//未訪問かつ、辺の重みが最小となるuを選ぶ
			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 && M[u][v] != INFTY {
				if d[v] > M[u][v] {
					d[v] = M[u][v]
					p[v] = u
					color[v] = GRAY
				}
			}
		}
	}

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

func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {

		for j := 0; j < n; j++ {
			tmp := nextInt()
			if tmp == -1 {
				tmp = INFTY
			}
			M[i][j] = tmp
		}

	}

	fmt.Println(prim())

}

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;

}