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 <queue>
#include <utility>
#include <functional>
#include <vector>
using namespace std;
int cost[100][100];
int prim(int n,int s){
	typedef pair<int,int> P;
	bool ischeck[n];
	int mincost = 0;
	priority_queue<P,vector<P>,greater<P> > pq;
	P p,tp;
	for(int i = 0;i < n;++i){
		ischeck[i] = false;
		if(cost[s][i] != -1){
			p.first = cost[s][i];
			p.second = i;
			pq.push(p);
		}
	}
	ischeck[s] = true;
	while(!pq.empty()){
		p = pq.top();
		pq.pop();
		if(ischeck[p.second]) continue;
		else{
			ischeck[p.second] = true;
			mincost += p.first;
			for(int i = 0;i < n;++i){
				if(cost[p.second][i] != -1){
					tp.first = cost[p.second][i];
					tp.second = i;
					pq.push(tp);
				}
			}
		}
	}
	return mincost;
}
int main(){
	int n;
	cin >> n;
	for(int i = 0;i < n;++i){
		for(int j = 0;j < n;++j){
			cin >> cost[i][j];
		}
	}
	cout << prim(n,0) << endl;
}

C++: #include <stdio.h>
#include <limits.h>
int n,M[100][100];
int prim();
int main(){
  int i,j,w;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&w);
      if(w==-1)M[i][j]=INT_MAX;
      else M[i][j]=w;
    }
  }
  printf("%d\n",prim());
  return 0;
}
int prim(){
  int sum,i,u,mincost,C[100],d[100],p[100];
  for(i=0;i<n;i++){
    d[i]=INT_MAX;
    C[i]=0;
    p[i]=-1;
  }
  d[0]=0;
  while(1){
    u=-1;
    mincost=INT_MAX;
    for(i=0;i<n;i++){
      if(C[i]!=2&&d[i]<mincost){
        mincost=d[i];
        u=i;
      }
    }
    if(u==-1)break;
    C[u]=2;
    for(i=0;i<n;i++){
      if(C[i]!=2&&M[u][i]!=INT_MAX){
        if(d[i]>M[u][i]){
          d[i]=M[u][i];
          p[i]=u;
          C[i]=1;
        }
      }
    }
  }
  sum=0;
  for(i=0;i<n;i++){
    if(p[i]!=-1)sum+=M[i][p[i]];
  }
  return sum;
}

C++: #include <algorithm>
#include <iostream>
#include <set>
#include <vector>

class TEdge;
struct TNode
{
	int TreeIndex;
	std::set<const TEdge*> Connected;
	
	TNode();
	void SetIndex(int Index, const TEdge* Edge);
};

class TEdge
{
	std::pair<TNode*, TNode*> FEnds;
	int FWeight;
public:
	TEdge(TNode* EndA, TNode* EndB, int Weight);
	
	bool operator<(const TEdge& Other)const;
	int  Weight()const {return FWeight;}
	bool ToMekeCycle()const;
	
	void JoinTree(int TreeIndex)const;
};

TNode::TNode()
:TreeIndex(0)
{
}

void TNode::SetIndex(int Index, const TEdge* Edge)
{
	if(TreeIndex >= Index) return;
	TreeIndex = Index;
	for(std::set<const TEdge*>::const_iterator It = Connected.begin(); It != Connected.end(); ++It){
		(*It)->JoinTree(Index);
	}
	Connected.insert(Edge);
}

TEdge::TEdge(TNode* EndA, TNode* EndB, int Weight)
:FEnds(EndA, EndB), FWeight(Weight)
{
}

bool TEdge::operator<(const TEdge& Other)const
{
	return Weight() < Other.Weight();
}

bool TEdge::ToMekeCycle()const
{
	return FEnds.first->TreeIndex > 0 && FEnds.first->TreeIndex == FEnds.second->TreeIndex;
}

void TEdge::JoinTree(int TreeIndex)const
{
	FEnds.first->SetIndex(TreeIndex, this);
	FEnds.second->SetIndex(TreeIndex, this);
}

class TGraph
{
	std::vector<TNode> FNodes;
	std::vector<TEdge> FEdges;
public:
	TGraph(int NodeCount);
	
	void AddEdge(int NodeIndexA, int NodeIndexB, int Weight);
	int WeightMinimumSpanningTree();
};

TGraph::TGraph(int NodeCount)
:FNodes(NodeCount)
{
}

void TGraph::AddEdge(int NodeIndexA, int NodeIndexB, int Weight)
{
	if(NodeIndexA <= NodeIndexB || Weight < 0) return;
	FEdges.push_back(TEdge(&FNodes[NodeIndexA], &FNodes[NodeIndexB], Weight));
}

int TGraph::WeightMinimumSpanningTree()
{
	std::sort(FEdges.begin(), FEdges.end());
	unsigned int TreeCount = 0;
	int Weight = 0;
	for(std::vector<TEdge>::iterator It = FEdges.begin(); It != FEdges.end() && TreeCount < FNodes.size() - 1; ++It){
		if(It->ToMekeCycle()) continue;
		It->JoinTree(TreeCount + 1);
		Weight += It->Weight();
		++TreeCount;
	}
	return Weight;
}

int main()
{
	int NodeCount;
	std::cin >> NodeCount;
	TGraph Graph(NodeCount);
	
	for(int i = 0; i < NodeCount; ++i)
	{
		for(int j = 0; j < NodeCount; ++j){
			int Weight;
			std::cin >> Weight;
			Graph.AddEdge(i, j, Weight);
		}
	}
	
	std::cout << Graph.WeightMinimumSpanningTree() << std::endl;
	return 0;
}

C++: // Graph II - Minimum Spanning Tree
// 問題URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_A&lang=jp
//
// 使うライブラリも多く、難しく感じた...
#include <iostream>
#include <algorithm>

using namespace std;

int n, buff, cost[101][101]={}, P[101], M = 0, ans = 0;
pair<int, int> edges[10010], vertices[10010];

void init(int n){
  for(int i = 0; i < n; ++i){
    P[i] = i;
  }
}

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

bool is_same_set(int x, int y){
  return root(x) == root(y);
}

void unite(int x, int y){
  P[root(x)] = root(y);
}

int main(){
  cin >> n;

  for(int row = 0; row < n; ++row){
    for(int col = 0; col < n; ++col){
      cin >> buff;
      cost[row][col] = buff; //隣接行列の読込
    }
  }

  for(int row = 0; row < n; ++row){
    for(int col = 0; col < row; ++col){
      if(cost[row][col]>0){
        edges[M].first = cost[row][col];
        edges[M].second = M;
        //cout << M << ": (" << row << ", " << col << ") = " << edges[M].first << endl;
        vertices[M].first = row, vertices[M].second = col;
        M++; //辺の数を管理、idとして利用
      }
    }
  }

  init(n);

  sort(edges, edges+M); //重みの小さい順に整列

  for(int i = 0; i <= M; ++i){
    int index = edges[i].second; //辺のidを取り出す
    if(!is_same_set(vertices[index].first, vertices[index].second)){ //辺の両端が繋がっていなければ
      unite(vertices[index].first, vertices[index].second); //両端を繋げる
      cout << "unite " << vertices[index].first << " and " << vertices[index].second << endl;
      ans += edges[i].first; //コストを加える
    }
  }
  cout << ans << endl;
}