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<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
#define pb push_back
#define int long long
#define MAX 100
#define NIL -1
using namespace std;
const int INF=1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int M[102][102];
int mincos[102];
bool used[102];
int n;

int prim(){
  rep(i,n){
    mincos[i]=INF;
    used[i]=false;
  }
  mincos[0]=0;
  int sum=0;
  while(1){
    int  v=-1;
    rep(i,n){
      if(used[i]==false&&(v==-1||mincos[i]<mincos[v]))v=i;
    }
    if(v==-1)break;
    used[v]=true;
    sum+=mincos[v];
    rep(i,n)mincos[i]=min(mincos[i],M[v][i]);
  }
  return sum;
}

signed main(){
  cin>>n;
  rep(i,n)rep(j,n){
    int e;
    cin>>e;
    M[i][j]=(e==-1?INF:e);
  }
  cout<<prim()<<endl;

  return 0;
}

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

using namespace std;

#define MAX_V 100
#define MAX_E 10000

int par[MAX_V],rank[MAX_V];
int V,E;

struct edge{ int u,v,cost; };
edge es[MAX_E];

bool comp(const edge &e1, const edge &e2){
  return e1.cost < e2.cost;
}

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

int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);

  if(x == y){
    return;
  }

  if(rank[x] < rank[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rank[x] == rank[y]){
      rank[x]++;
    } 
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}

int kruskal(){
  sort(es, es + E, comp);

  init(V);
  int res = 0;

  for(int i = 0 ; i < E ; i++){
    edge e = es[i];

    if(!same(e.u,e.v)){
      unite(e.u,e.v);
      res += e.cost;
    }
  }
  return res;
}

int main(){
  int c;

  cin >> V;
  for(int i = 0 ; i < V ; i++){
    for(int j = 0 ; j < V ; j++){
      cin >> c;

      if(c == -1){
	continue;
      }

      edge e = {i,j,c};
      es[E++] = e;
    }
  }

  cout << kruskal() << endl; 

  return 0;
}

C++: #include<bits/stdc++.h>
#include<limits.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)

#define MAX 101

int total_cost = 0;

vector<vector<int>> adj_mat(MAX, vector<int>(MAX, INT_MAX));

int find_node(vector<int> cost){
    int node;
    int min = INT_MAX;
    rep(i, cost.size()){
        if(cost.at(i) < min){
            node = i;
            min = cost.at(i);
        }
    }
    total_cost += min;

    return node;
}

void prim(int node_size){
    int node = 0;
    vector<int> U(node_size, 0);  // 最小全域木に含まれない頂点
    vector<int> cost(node_size); //構築中の木と未処理ノードvの間のコスト

    // cost, nearestNodeの初期化
    rep(i, node_size){
        cost.at(i) = adj_mat.at(node).at(i);
    }

    // rep(i, node_size) cout << cost.at(i) << " ";
    // cout << endl;

    U.at(node) = 1; //nodeは処理済み

    while(accumulate(U.begin(), U.end(), 0) != node_size){
        // 構築中の木に一番近いノードを探す
        int x = find_node(cost);
        // cout << "add node :" << x << endl;
        U.at(x) = 1;

        cost.at(x) = INT_MAX; // 自分自身へのコストは無限大とする

        rep(i, node_size){
            if(U.at(i) == 1){
                continue;
            }
            // 未処理ノードと新たに加えたノードとの距離が、以前のcostよりも小さい場合、更新
            if(adj_mat.at(x).at(i) < cost.at(i)){
                cost.at(i) = adj_mat.at(x).at(i);
            }
        }
        // rep(i, node_size) cout << cost.at(i) << " ";
        // cout << endl;
    }
} 

int main(){
    int n; cin >> n;
    rep(i, n){
        rep(j, n){
            cin >> adj_mat.at(i).at(j);
            if(adj_mat.at(i).at(j) == -1){
                adj_mat.at(i).at(j) = INT_MAX;
            }
        }
    }


    prim(n);
    cout << total_cost << endl;
}

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

int table[100][100];
int d[100];//????°??????¢
bool used[100];
int v;
const int INF = 10000000;

int prim(){
  fill(d,d+v,INF);
  fill(used,used+v,false);
  d[0] = 0;
  int res = 0;

  while(1){
    int k=-1;
    //???????±???????????????????????????????????????????????????????????°?????????????????????¢???
    for(int i=0;i<v;i++){
      if(!used[i] && (k==-1 || d[i] < d[k])) k=i;
    }

    if(k==-1) break;
    used[k] = true;
    res += d[k];

    for(int i=0;i<v;i++){
      if(table[k][i] != -1){
        d[i] = min(d[i],table[k][i]);
      }
    }
  }
  return res;
}

int main(){

    cin >> v;

    for(int i=0;i<v;i++){
      for(int j=0;j<v;j++){
        cin >> table[i][j];
      }
    }

    cout << prim() << endl;

    return 0;
}

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

using namespace std;

int P[100000];

struct Line{
  int a, b, weight;
};

bool lineCompare(Line a, Line b){return a.weight < b.weight;}

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

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

int unite_sum(Line x){
  int sum = 0;
  if(root(x.a) != root(x.b)){
    P[root(x.a)] = root(x.b);
    sum += x.weight;
  }
  return sum;
}

bool is_in_the_same_tree(int a, int b){
  return root(a) == root(b);
}


int main(){
  int n, i, j, k, sum;
  cin >> n;
  init(n);
  Line lines[n*n];
  k = 0;
  for (i = 0; i < n; ++i){
    for (j = 0; j < n; ++j){
      Line line;
      line.a = i;
      line.b = j;
      cin >> line.weight;
      lines[k] = line;
      k++;
    }
  }
  sort(lines, lines+n*n, lineCompare);
  
  sum = 0;
  for (i = 0; i < n*n; ++i){
    if(lines[i].weight == -1){
      continue;
    }else{
      sum += unite_sum(lines[i]);
    }
  }
  cout << sum << endl;
}

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

int main(void)
{
	int n, now = 0, flag[101] = {};
	long ans = 0, an[100][100], min[100];

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> an[i][j];
		min[i] = MAX;
	}

	do {
		long key = MAX, key_i;
		flag[now] = 1;
		flag[100] = 0;

		for (int i = 0; i < n; i++) {
			if (an[now][i] != -1 && an[now][i] < min[i] && flag[i] == 0)
				min[i] = an[now][i];
			if (flag[i] == 0 && min[i] < key) {
				key = min[i];
				key_i = i;
			}
			if (flag[i] == 1)
				flag[100]++;
		}

		now = key_i;
		ans += key;

	} while (flag[100] != n - 1);

	cout << ans << endl;

	return 0;
}