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 <utility>
#include <algorithm>
using namespace std;

int m,n,x,ans;
int P[100+10],edge1[2000+10],edge2[2000+10];


int root(int a){
	if (P[a] == a) return a;
	return (P[a] = root(P[a]));
}

bool same(int a, int b){
	return root(a)==root(b);
}
	
void unite(int a, int b){
	P[root(a)] = root(b);
}

int main() {
	pair<int,int> edges[2000+10];
	cin >> n;
	
	for (int i=1; i<=n; i++){
		P[i] = i;
	}
	
	m = 0;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			cin >> x;
			if (x>-1){
				edge1[m] = i;
				edge2[m] = j;
				edges[m] = make_pair(x, m);
				m+=1;
			}
		}
	}
	
	sort(edges, edges+m);
	
	for (int i=0; i<m; i++){
		if (!same(edge1[edges[i].second], edge2[edges[i].second])){
			unite(edge1[edges[i].second], edge2[edges[i].second]);
			ans += edges[i].first;
		}
	}
	
	cout << ans << endl;
	
}

C++: #include <bits/stdc++.h>

#define INFTY 1000001
#define MAX 100

class Edge{
public:
    int target, cost;
    Edge(int target = 0, int cost = 0) : target(target), cost(cost) {}
};

std::vector<Edge> G[MAX];
bool visited[MAX];
int parent[MAX], key[MAX];
int V, minv, min_index;

int minKey() {
    minv = INFTY;
    for (int v = 0; v < V; v++)
        if (!visited[v] && key[v] < minv)
            minv= key[v], min_index = v;
    return min_index;
}


void printMST()
{
    int sum = 0;
    for (int i = 1; i < V; i++)
        sum += key[i];
    std::printf("%d\n", sum);

}

void prim() {

    for (int i = 0; i < V; i++) {
        key[i] = INFTY;
        visited[i] = false;
    }
    key[0] = 0;
    parent[0] = -1;

    int current, target, cost;

    for (int i = 0; i < V-1; i++) {
        current = minKey();
        visited[current] = true;

        for (unsigned long v = 0; v < G[current].size(); v++) {
            target = G[current][v].target;
            cost = G[current][v].cost;
            if (!visited[target] && cost < key[target])
                parent[target] = current, key[target] = cost;
        }
    }
    printMST();

}


int main()
{
    std::scanf("%d", &V);
    int cost;

    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            std::scanf("%d", &cost);
            if (cost != -1) G[i].push_back(Edge(j, cost));
        }
    }

    prim();
    return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

// ---------------------
// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

// ---------------------
#define INF 922337203685477580
typedef long long ll;

int main() {
  int n;
  cin >> n;

  int G[n][n];
  int visited[n];
  int d[n];
  int p[n];
  REP(y, n) {
    REP(x, n) {
      int cost;
      cin >> cost;

      if (cost == -1) {
        G[y][x] = 1 << 15;
      } else {
        G[y][x] = cost;
      }
    }
    visited[y] = 0;
    d[y] = 1 << 15;
    p[y] = -1;
  }

  d[0] = 0;

  REP(_, n) {
    int mincost = 1 << 15;
    int minv;
    REP(v, n) {
      if (!visited[v] && d[v] < mincost) {
        minv = v;
      }
    }
    visited[minv] = 1;
    REP(to, n) {
      if (G[minv][to] < (1 << 15) && G[minv][to] < d[to]) {
        d[to] = G[minv][to];
        p[to] = minv;
      }
    }
  }

  ll sum = 0;
  REP(i, n) {
    if (p[i] != -1) {
      sum += G[i][p[i]];
    }
  }

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

C++: #include<iostream>
using namespace std;
static const int MAX=100;
static const int INFTY=(1<<21);
static const int white=0;
static const int gray=1;
static const int black=2;

int n,M[MAX][MAX];

int prim(){
    int n,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]!=balck&&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(){
    cin>>n;
    for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
	    int e;
	    cin>>e;
	    M[i][j]=(e==-1)?INFTY:e;
	}
    }
    cout<<prim()<<endl;
    return 0;
}

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

#define INFTY 2001
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define N 100

// 最小全域木を構成し、重みの総和を返す関数
int prim(int n, int A[N][N]) {
  int i, vertex, min_cost, sum_weight, cost[N], color[N];
  // 初期化
  for (i = 0; i < n; i++) {
    cost[i] = INFTY;
    color[i] = WHITE;
  }
  cost[0] = 0;
  color[0] = GRAY;
  sum_weight = 0;
  
  while (1) {
    // Tに隣接する頂点の中で最小のコストを持つものを選ぶ
    vertex = -1;
    min_cost = INFTY;
    for (i = 0; i < n; i++) {
      if (color[i] == GRAY && cost[i] < min_cost) {
        min_cost = cost[i];
        vertex = i;
      }      
    }
    // T = V ならば終了
    if (vertex == -1) break;

    color[vertex] = BLACK;  // vertexをTに加える
    sum_weight += cost[vertex];

    // vertexに隣接し、Tに属していない頂点のコストを更新
    for (i = 0; i < n; i++) {
      if (color[i] != BLACK && A[vertex][i] < INFTY) {
        color[i] = GRAY;
        if (cost[i] > A[vertex][i]) cost[i] = A[vertex][i];
      }
    }
  }

  return sum_weight;
}


// 最小全域木の辺の重みの和を計算する関数
int sum_weight(int n, int parent[], int A[N][N]) {
  int sum = 0;
  
  for (int i = 1; i < n; i++) sum += A[i][parent[i]];
  
  return sum;
}

int main() {
  int i, j, n, w, A[N][N];

  cin >> n;
  // 隣接行列が与えられる
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      cin >> w;
      if (w == -1) A[i][j] = INFTY;
      else A[i][j] = w;
    }
  }

  cout << prim(n, A) << endl;

  return 0;
}