Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

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

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	seen := make([]bool, n)
	for i := range list {
		list[i] = make([]int, n)
		for j := range list[i] {
			list[i][j] = scanInt()
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	sum := 0
	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if seen[node.id] {
			continue
		}
		seen[node.id] = true
		sum += node.weight

		for i, w := range list[node.id] {
			if w < 0 {
				continue
			}
			heap.Push(h, Node{id: i, weight: w})
		}
	}

	fmt.Println(sum)
}

C++: #include <iostream>
#include <stdio.h>
#define MAX 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, M[MAX][MAX];

int prim() {
    int u, 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 (color[i] != BLACK && d[i] < minv) {
                u = i;
                minv = d[i];
            }
        }
        if (u == -1) break;
        color[u] = BLACK;
        for (int 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;
                }
            }
        }
    }
    
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (p[i] != -1) sum += M[i][p[i]];
    }
    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int e; std::cin >> e;
            M[i][j] = (e != -1) ? e : INFTY;
        }
    }
    
    printf("%d\n", prim());
    
    return 0;
}

C++: /*
* @Author: Samson
* @Date:   2018-06-12 18:24:44
* @Last Modified by:   Samson
* @Last Modified time: 2018-06-13 12:00:47
*/
//   @URL : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_A
#include<bits/stdc++.h>
#include<algorithm>
#include <cstdlib>
#define white 0
#define gray 1
#define black 2
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int MAXN = 1e3+10;

int p[MAXN],color[MAXN],a[MAXN][MAXN],t,n,d[MAXN];

int prim()
{
	int minv,u,v;
	for(int i = 1; i <= n; ++i)
	{
		d[i] = INF;
		p[i] = -1;
		color[i] = white;
	}
	
	d[1] = 0;

	while(1)
	{
		minv = INF;
		u = -1;
		for(int i = 1; i <= n; ++i)
		{
			if(minv > d[i] && color[i] != black)
				minv = d[i],u = i;
		}
		if(u == -1)	break;
		color[u] = black;
		for(int v = 1; v <= n; ++v)
		{
			if(color[v] != black && a[u][v] != INF)
			{
				if(d[v] > a[u][v])
				{
					d[v] = a[u][v];
					p[v] = u;
					color[v] = gray;
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i)
		if(p[i] != -1)
			ans += a[i][p[i]];
	return ans;
}

int main(void)
{
	ios::sync_with_stdio(false); 
	//cin.tie(0);
	cin>>n;
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
		{
			cin>>t;
			a[i][j] = t==-1?INF:t;
		}
	}
	cout<<prim()<<'\n';
	return 0;
}

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

int root(int i,vector<int> &parent){
    if(parent[i]==-1){
        //親がいない時
        return i;
    }else{
        int result=root(parent[i],parent);
        parent[i]=result; //パス圧縮
        return result;
    }
}

void unite(int x,int y,vector<int> &parent){
    if(root(x,parent)!=root(y,parent)){
        parent[root(y,parent)]=root(x,parent);
    }
}

bool issame(int x,int y,vector<int> &parent){
    return root(x,parent)==root(y,parent);
}

int main(){
    int n;
    cin >> n;
    //first:cost,second:(first:from,second:to)
    vector<pair<int,pair<int,int> > > bridges(n*n);

    //入力
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            int cost;
            if(cin >> cost,cost!=-1){
                bridges.push_back(pair<int,pair<int,int> >(cost,pair<int,int>(i,j)));
            }
        }
    }

    //sort
    sort(bridges.begin(),bridges.end());

    //島を管理する用
    vector<int> parents(n*n,-1);

    int sum=0;

    for(int i=0;i<bridges.size();++i){
        if(!issame(bridges[i].second.first,bridges[i].second.second,parents)){
            unite(bridges[i].second.first,bridges[i].second.second,parents);
            sum+=bridges[i].first;
        }
    }
    cout << sum << endl;
}

C++: #include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef vector <int> vi;
typedef vector <vi> vvi;
struct edge{
	int from;
	int to;
};
typedef multimap <int, edge, less<int> > mme;

int addedge(vvi &graph, int y, int x, int val=1){
	graph[y][x] = val;
	return val;
}

int make_graph(vvi &graph, vi &stamp){
	int n=graph.size(), val;

	for (int j=0; j<n; j++){
		for (int i=0; i<n; i++){
			cin>>val;
			addedge(graph, i, j, val);
		}
		stamp[j] = 0;
	}
	return 0;
}

int Minimum_Spanning_Tree(vvi &graph, vi &stamp){

	mme edges;
	int n = graph.size(), p1, p2, p3, total=0;
	p1=0;
	stamp[p1] = 1;

	while (p1!=-1){
		for (int p2=0; p2<n; p2++){
			int *tmp=&graph[p1][p2];
			if (*tmp!=-1 && stamp[p2]==0){
				edge e;
				e.from = p1;
				e.to = p2;
				edges.insert(pair <int, edge> (*tmp, e));
			}
		}
		p1=-1;
		while (! edges.empty()){
			mme::iterator const it = edges.begin();
			if (stamp[it->second.from]==1 && stamp[it->second.to]==0){
				p1 = it->second.to;
				stamp[p1]=1;
				total+=it->first;
				edges.erase(it);
				break;
			}
			edges.erase(it);
		}
	}
	return total;
}

int resultout(vvi &graph){
	for (int i=0; i<int(graph.size()); i++){
		for (int j=0; j<int(graph.size()); j++){
		cout<<graph[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

int main(void){

	int n, row;
	cin>>n;
	vvi G(n, vi(n));
	vi stamp(n);

	make_graph(G, stamp);

	cout<<Minimum_Spanning_Tree(G, stamp)<<endl;

	return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; i++)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int INF = 1 << 30;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100;

vector<pii> G[N];
bool T[N];

int main() {
	int n; cin >> n;
	rep(i, n) { rep(j, n) {
		int a; cin >> a;
		if (a == -1) continue;
		G[i].push_back(pii(a, j));
	} }
	rep(i, n) T[i] = false;

	int ans = 0;
	priority_queue<pii, vector<pii>, greater<pii>> Q;
	Q.push(pii(0, 0));
	while (!Q.empty()) {
		pii p = Q.top(); Q.pop();
		if (T[p.second]) continue;
		ans += p.first;
		T[p.second] = true;
		for (auto i : G[p.second]) Q.push(i);
	}
	cout << ans << endl;
}