Go: package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

type ElementKey int
type Node struct {
	key    ElementKey
	parent *Node
	rank   int
}

func newNode(key ElementKey) *Node {
	node := Node{}
	node.key = key
	node.parent = &node
	node.rank = 0

	return &node
}

func union(x, y *Node) {
	xSet := findSet(x)
	ySet := findSet(y)
	link(xSet, ySet)
}

func link(x, y *Node) {
	if x.rank > y.rank {
		y.parent = x
	} else {
		x.parent = y

		if x.rank == y.rank {
			y.rank++
		}
	}
}

func findSet(x *Node) *Node {
	if x != x.parent {
		x.parent = findSet(x.parent)
	}
	return x.parent
}

func newDisjointSets(nSets int) *DisjointSets {
	sets := DisjointSets{}
	sets.keyToNode = map[ElementKey]*Node{}
	for i := 0; i < nSets; i++ {
		key := ElementKey(i)
		sets.keyToNode[key] = newNode(key)
	}
	return &sets
}

type DisjointSets struct {
	keyToNode map[ElementKey]*Node
}

func (sets *DisjointSets) union(x, y ElementKey) {
	xNode := sets.keyToNode[x]
	yNode := sets.keyToNode[y]
	union(xNode, yNode)
}

func (sets DisjointSets) findSet(x ElementKey) *Node {
	xNode := sets.keyToNode[x]
	return findSet(xNode)
}

type Edge struct {
	i, j   int
	weight int
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	sets := newDisjointSets(n)
	edges := []Edge{}
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, n)
		for j := 0; j < n; j++ {
			a[i][j] = nextInt()
			if a[i][j] >= 0 {
				e := Edge{
					i:      i,
					j:      j,
					weight: a[i][j],
				}
				edges = append(edges, e)
			}
		}
	}
	sort.Slice(edges, func(i, j int) bool { return edges[i].weight < edges[j].weight })
	totalWeight := 0
	for _, edge := range edges {
		i := ElementKey(edge.i)
		j := ElementKey(edge.j)
		if sets.findSet(i) != sets.findSet(j) {
			totalWeight += edge.weight
			sets.union(i, j)
		}
	}
	fmt.Println(totalWeight)
}

C++: #include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
using namespace std;

int main(){
	
	int n;
	cin>>n;
	vector<vector<int>> a(n);
	rep(i,n){
		a[i].resize(n);
		rep(j,n){
			cin>>a[i][j];
			if(a[i][j]==-1)a[i][j]=INF;
		}
	}
	vector<int> t(n);
	rep(i,n){
		t[i]=0;
	}
	t[0]=1;
	int ans=0;
	rep(ii,n-1){
		int m=100000;
		int pm;
		rep(i,n){
			rep(j,n){
				if(t[i]==1 && t[j]==0 && m>a[i][j]){
					m=a[i][j];
					pm=j;
				}
			}
		}
		t[pm]=1;
		ans+=m;
	}
	cout<<ans<<endl;
	
}

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;
}