Go: package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	matrix   []int // 隣接行列
	minToMst int   // MSTへの重み最小値
	parent   int   // 最小値の相手
	color    color
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i].matrix = eAtoi((strings.Fields(eGetline(scanner))))
		nodes[i].parent = -1
		nodes[i].minToMst = math.MaxInt16
		nodes[i].color = white
	}

	// 初回はnode[0]がMSTに入るように,minToMstを設定
	nodes[0].minToMst = 0
	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか
		min := math.MaxInt16
		u := -1
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].minToMst < min {
				u = i
				min = nodes[i].minToMst
			}
		}

		if u == -1 {
			break
		}
		// MSTに追加する頂点決定
		nodes[u].color = mst

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みを更新
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].matrix[u] == -1 {
				// 接してない
				continue
			}
			if nodes[i].matrix[u] < nodes[i].minToMst {
				// node[u]との重みが最小
				nodes[i].minToMst = nodes[i].matrix[u]
				nodes[i].parent = u
			}
		}
	}

	sum := 0
	for _, v := range nodes {
		// node[0]はparentが入っていない
		if v.parent != -1 {
			sum += v.matrix[v.parent]
		}
	}
	fmt.Println(sum)
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

C++: #include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
using namespace std;

struct Edge{
  int src,dst;
  int weight;

  Edge(int src,int dst,int weight):
    src(src),dst(dst),weight(weight){}
};

bool operator < (const Edge &m,const Edge &n){
  return m.weight != n.weight ? m.weight > n.weight :
    m.src != n.src ? m.src < n.src : m.dst < n.dst;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int MST(priority_queue<Edge>,int);
bool check(int[][100],int,int,int);//src,dstで結ばれる線を追加した時、グラフは閉路かどうかのチェック関数

int main(int argc,char* argv[]){
  int n,val;
  priority_queue<Edge> que;

  cin>>n;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin>>val;
      que.push(Edge(i,j,val));
    }
  }

  cout<<MST(que,n)<<endl;
  return 0;
}

int MST(priority_queue<Edge> que,int n){
  int ans=0;
  int flag[100][100];
  set<int> s;
  memset(flag,0,sizeof(flag[100][100]));

  while((int)s.size()!=n){
    Edge tmp(0,0,0);
    int ftmp[100][100];
    tmp=que.top();que.pop();
    memcpy(ftmp,flag,sizeof(flag));

    if(tmp.weight!=-1 && flag[tmp.src][tmp.dst]!=1){
      if(check(ftmp,tmp.src,tmp.dst,n)){
	flag[tmp.src][tmp.dst]=1;flag[tmp.dst][tmp.src]=1;
	s.insert(tmp.src);s.insert(tmp.dst);
	ans+=tmp.weight;
      }
    }
  }
  return ans;
}

bool check(int flag[][100],int src,int dst,int n){
  flag[src][dst]=1;
  queue<int> que;
  que.push(src);
  while(!que.empty()){
    int tmp=que.front();que.pop();

    for(int i=1;i<=n;i++){
      if(flag[tmp][i]==1){
	flag[tmp][i]=0;flag[i][tmp]=0;
	que.push(i);
      }
    }
    if(que.front()==src)
      return false;
  }

  return true;
}

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

const int N = 100;
int n;
int A[N][N];
priority_queue< pair<int, int> > Q;

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

	int mcost = -INT_MAX;

	for (int i=0; i<n; i++)
	{
		bool visit[N] = {0};

		Q.push(pair<int, int>(0,i));

		int cost = 0;

		while (Q.size())
		{
			pair<int, int> q = Q.top();
			Q.pop();
			int k = q.second;
			if (visit[k]) continue;
			cost += q.first;
			visit[k]=true;
			for(int j=0;j<n;j++)
			{
				int c = A[k][j];
				if (c <= 0) continue;
				if (visit[j]) continue;
				Q.push(pair<int, int>(-c,j));
			}
		}

//		cout << i << ' ' << -cost << endl;

		if (mcost < cost) mcost = cost;
	}

	cout << -mcost << endl;
		
	return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define repp(i, m, n) for(int i = m; i < n; i++)
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int, int> pai;
typedef pair<ll,ll> pal;
int e[101][101];
int t;
pai edge[10001];
int c[10001];
int sz[10001];
int n;
int P[10001];
int ans;
int x, y;
void init(int k)
{
    repp(i, 1, k+1)
    {
        P[i]=i;
        sz[i]=1;
    }
}
int root(int a)
{
    if(P[a]==a)
    {
        return a;
    }
    else
    {
        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)
{
    if(sz[root(a)]<sz[root(b)])
    {
        swap(a, b);
    }
    sz[root(a)]+=sz[root(b)];
    P[root(b)]=root(a);
}
int main()
{
    cin >> n;
    rep(i, n)
    {
        rep(j, n)
        {
            cin >> e[i+1][j+1];
        }
    }
    t=0;
    rep(i, n)
    {
        repp(j, i+1, n)
        {
            if((i<j)&&(e[i+1][j+1]!=-1))
            {
                edge[t]=make_pair(e[i+1][j+1]*1000+i+1, j+1);
                //cout << edge[t].first << ' ' << j+1 << ' ' << t << endl;
                t++;
            }
        }
    }
    sort(edge, edge+t);
    //rep(i, t)
    //{
    //	cout << edge[i].first << ' ' << edge[i].second << endl;
    //}
    rep(i, t)
    {
        c[i]=edge[i].first / 1000;
        edge[i]=make_pair(edge[i].first%1000, edge[i].second);
        // cout << c[i] << ' ' << edge[i].first << ' ' << edge[i].second << endl;
    }
    init(n);
    ans=0;
    rep(i, t)
    {
    if(!is_same_set(edge[i].first, edge[i].second))
        {
            unite(edge[i].first, edge[i].second);
            ans+=c[i];
            // cout << edge[i].first << ' ' << edge[i].second << ' ' << i << ' ' << ans << endl;
        }
    }
    cout << ans << endl;
    return 0;
}

C++: #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 105
int matrix[N][N];
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_A
//spanning tree tree
bool power[N]; // start from 1;
int main(){
	int n;
	scanf("%d",&n);
	memset(matrix, 0,sizeof(matrix));
	memset(power,0,sizeof(power));
	for(int i = 1; i<=n; i++){
		for(int j = 1; j<=n; j++){
			scanf("%d",&matrix[i][j]);//-1 means nothing
		}
	}
	int count = 0;
	int res = 0;
	int min = 2005;
	while(count<n-1){
		//find minmila ele from matrix
		int v1 = 0,v2 = 0;
		min = 2005;
		for(int i = 1; i<=n;i++){
			for(int j = 1;j<=n; j++){
				if(matrix[i][j]!=-1 && matrix[i][j]<min){
					if(count==0){
						if(power[i] == 0 && power[j]==0) {
							v1 = i;v2 = j;
							//printf("i:%d j:%d\n",i,j);
							min = matrix[i][j];
						}
						//continue;
					}else {
							if((power[i] == 1 && power[j]==0)||(power[i] == 0 && power[j]==1)){
							v1 = i;v2 = j;
							min = matrix[i][j];
						}
					}
					
				}
			}
		}
		//printf("min:%d\n",min);
		matrix[v1][v2] = -1;
		power[v1] = 1;
		power[v2] = 1;
		res+=min;
		count++;
	}
	printf("%d\n",res);
	return 0;
}