Go: package main

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

const R = 100000000

var sc = bufio.NewScanner(os.Stdin)

var n int
var A [101][101]int

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func prim() int {
	var u, Minimum, sum int
	var d, p, color [101]int

	for i := 0; i < n; i++ {
		d[i] = R
		p[i] = -1
		color[i] = 0
	}
	d[0] = 0

	for {
		Minimum = R
		u = -1
		for i := 0; i < n; i++ {
			if Minimum > d[i] && color[i] != 2 {
				u = i
				Minimum = d[i]
			}
		}
		if u == -1 {
			break
		}
		color[u] = 2
		for j := 0; j < n; j++ {
			if color[j] != 2 && A[u][j] != R {
				if d[j] > A[u][j] {
					d[j] = A[u][j]
					p[j] = u
					color[j] = 1
				}
			}
		}
	}

	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += A[i][p[i]]
		}
	}
	return sum
}
func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			e := nextInt()
			if e == -1 {
				A[i][j] = R
			} else {
				A[i][j] = e
			}
		}
	}
	fmt.Println(prim())
}

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

C++: #include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <utility>
#include <functional>
#include <numeric>

template <class T>
using vec = std::vector<T>;

constexpr int nil = -1;
constexpr int inf = 1 << 30;

struct Edge
{
    int to;
    int cost;
};

int prim(const vec<vec<Edge>>& edges)
{
    const int n = edges.size();
    vec<bool> reached(n);
    vec<int> parents(n, nil);
    vec<int> distances(n, inf);

    distances[0] = 0;

    while (true)
    {
        int minCost {inf};
        int u {};
        
        for (int i = 0; i < n; ++i)
        {
            if (!reached[i] && distances[i] < minCost)
            {
                u = i;
                minCost = distances[i];
            }
        }
        
        if (minCost == inf)
            break;

        reached[u] = true;

        for (auto e : edges[u])
        {
            if (!reached[e.to])
            {
                if (e.cost < distances[e.to])
                {
                    distances[e.to] = e.cost;
                    parents[e.to] = u;
                }
            }
        }
    }

    int sum = std::accumulate(distances.begin(), distances.end(), 0);

    return sum;
}

void solve()
{
    using namespace std;
    int n;
    cin >> n;

    //隣接リスト形式
    vec<vec<Edge>> edges(n);

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0, cost; j < n; ++j)
        {
            cin >> cost;
            if (cost != -1)
                edges[i].push_back({j, cost});
        }
    }

    cout << prim(edges) << endl;
}

int main()
{
    solve();
    return 0;
}