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