Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

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

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

const INF = 1 << 60

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	G := make([][]int, N)
	for i := 0; i < N; i++ {
		G[i] = make([]int, N)
		for j := 0; j < N; j++ {
			G[i][j] = sc.nextInt()
		}
	}
	d := make([]int, N)
	for i := 0; i < N; i++ {
		d[i] = INF
	}
	seen := make([]bool, N)
	d[0] = 0
	ans := 0
	for {
		cur := 0
		minCost := INF
		for i := 0; i < N; i++ {
			if !seen[i] && d[i] < minCost {
				minCost = d[i]
				cur = i
			}
		}
		if minCost == INF {
			break
		}
		seen[cur] = true
		ans += d[cur]
		for i := 0; i < N; i++ {
			cost := G[cur][i]
			if cost != -1 && cost < d[i] {
				d[i] = cost
			}
		}
	}

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;

#define REP(var, count) for(int var=0; var<count; var++)

struct unionf {
	
	vector<int> data;
	
	unionf(int n) {
		REP(i, n+1) { data.push_back(i); }
	}
	
	int root(int a) {
		if(data[a] == a) { return a; }
		return (data[a] = root(data[a]));
	}
	
	bool issame(int a, int b) {
		return root(a) == root(b);
	}
	
	void unite(int a, int b) {
		data[root(a)] = root(b);
	}

};

int main(void) {
	int N;
	cin >> N;
	
	vector<pair<int, pair<int, int> > > edge;
	
	REP(x, N) {
		REP(y, N) {
			int c;
			cin >> c;
			if ( x <= y ) { continue; }
			if ( c == -1 ) { continue; }
			edge.push_back( make_pair(c, make_pair(x,y)) );
		}
	}
	
	sort(edge.begin(), edge.end());
	
	unionf uf(N);
	
	int cnt = 0;
	int ret = 0;
	REP(i, edge.size() ) {
		
		pair<int, int> sd = edge[i].second;
		if ( ! uf.issame( sd.first, sd.second ) ) {
			cnt ++;
			ret += edge[i].first;
		}
		
		if ( cnt == N-1 ) { break; }
	}
	
	cout << ret << endl;
}

C++: #include<iostream>
using namespace std;
#define S 100
#define INF 2001
#define WHITE 0;
#define GRAY 1;
#define BLACK 2
int n,a[S][S];

int prim(){
    int u,mina;
    int d[S],p[S],cnd[S];

    for(int i=0;i<n;i++){
        d[i]=INF;
        p[i]=-1;
        cnd[i]=WHITE;
    }

    d[0]=0;
    while(1){
        mina=INF;
        u=-1;
        for(int i=0;i<n;i++){
            if(mina>d[i]&&cnd[i]!=BLACK){
                u=i;
                mina=d[i];
            }
        }
        if(u==-1)break;
        cnd[u]=BLACK;
        for(int v=0;v<n;v++){
            if(cnd[v]!=BLACK&&a[u][v]!=INF){
                if(d[v]>a[u][v]){
                    d[v]=a[u][v];
                    p[v]=u;
                    cnd[v]=GRAY;
                }
            }
        }
    }
            int sum=0;
        for(int i=0;i<n;i++){
            if(p[i]!=-1)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++){
            int e;
            cin>>e;
            if(e==-1)a[i][j]=INF;
            else a[i][j]=e;
        }
    }
    cout<<prim()<<endl;
    return 0;

}

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

#if 0
所用時間: 1h

感想: 思ったより実装すべきコード量が多かった。DisjointSetは今後も使う機会が多そうなので、クラス化してみた。
Pの配列を動的に確保するよう工夫した、良い復習になった。

#endif

int N, buff, M = 0, SUM = 0, A[101][101], cost[5000], dpt[5000], dst[5000];//A[Y][X]
vector<pair<int, int> > edges;

class disjointSet {
private:
    int* P;
    
public:
    disjointSet(){
        P = new int[100000];
    }
    disjointSet(int N){     
        P = new int[N];
    }
    ~disjointSet(){
        delete[] P;
    }

    void init(int N){ //木構造の初期化
        for(int i = 0; i <= N; ++i){
            P[i] = i;
        }
    }

    int root(int a){ //根の参照
        if(P[a] == a) return a;
        return (P[a] = root(P[a]));
    }

    bool is_same_set(int a, int b){ //同じ根か?
        return root(a) == root(b);
    }

    void unite(int a, int b){
        P[root(a)] = root(b); //aのrootをbの子にする
    }
};


void preprocess(){//辺の前処理
  for(int r = 0; r < N; ++r){
    for(int c = r+1; c < N; ++c){
      if (A[r][c] > -1) {
        cost[M] = A[r][c];
        dpt[M] = r;
        dst[M] = c;
        M++;
      }
    }
  }

  //for(int i = 0; i < M; ++i) cout << cost[i] << endl;

  for(int i = 0; i < M; ++i){
    edges.push_back(make_pair(cost[i], i));
  }
  for(int i = 0; i < M; ++i) cout << edges[i].first << " " << edges[i].second << endl;

  sort(edges.begin(), edges.end());

  for(int i = 0; i < M; ++i) cout << edges[i].first << " " << edges[i].second << endl;

}

void solve(){
  disjointSet Union(100000);

  int ans = 0;
  preprocess();

  Union.init(N);

  for(int i = 0; i < M; ++i){
    int index = edges[i].second;
    if(Union.is_same_set(dpt[index], dst[index])) continue;
    else {
      Union.unite(dpt[index], dst[index]);
      cout << "unite " << dpt[index] << " and " << dst[index] << endl;
      ans += cost[index];
    }
  }
  cout << ans << endl;
}

int main(){

cin >> N;

for(int i = 0; i < N; ++i){
  for(int j = 0; j < N; ++j){
    cin >> buff;
    A[i][j] = buff;
    }
  }

  //行列の表示
  // cout << "Matrix:" << endl;
  // for(int row=0; row < N; ++row){
  //   for(int col = 0; col < N; ++col){
  //     cout << A[row][col];
  //   }
  //   cout << endl;
  // }

  solve();
}

C++: #include<stdio.h>

int field[110][110];
int selected[110] = { 0 };
int v;

int prim()
{
	int no_edge = 0;
	int weight = 0;
	selected[0] = 1;
	int x, y;

	while (no_edge < v - 1)
	{
		int min = 0x7fffffff;
		for (int i = 0; i < v; i++)
		{
			if (selected[i])
				for (int j = 0; j < v; j++)
				{
					if (!selected[j] && field[i][j] != -1)
						if (min > field[i][j])
						{
							min = field[i][j];
							x = i;
							y = j;
						}
				}
		}
		weight += field[x][y];
		no_edge++;
		selected[y] = 1;
	}
	return weight;
}

int main()
{
	scanf("%d", &v);
	for (int i = 0; i < v; i++)
		for (int j = 0; j < v; j++)
			scanf("%d", &field[i][j]);
	printf("%d\n", prim());
}