Go: package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	I int
	J int
	A int
}

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]int, n)
	edges := make([]Edge, 0, n*(n-1)/2)
	parents := make([]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&g[i][j])
			if g[i][j] >= 0 {
				edges = append(edges, Edge{i, j, g[i][j]})
			}
		}
		parents[i] = i
	}
	sort.SliceStable(edges, func(i, j int) bool { return edges[i].A >= edges[j].A })

	sum := 0
	num := 0
	for len(edges) > 0 && num < n-1 {
		edge := edges[len(edges)-1]
		edges = edges[:len(edges)-1]

		if same(edge.I, edge.J, &parents) {
			continue
		}
		union(edge.I, edge.J, &parents)
		sum += edge.A
		num += 1
	}
	fmt.Println(sum)
}



func root(id int, parents *[]int) int {
	if id == (*parents)[id] {
		return id
	}
	return root((*parents)[id], parents)
}

func union(i, j int, parents *[]int) {
	(*parents)[root(j, parents)] = (*parents)[root(i, parents)]
}

func same(i, j int, parents *[]int) bool {
	return root(i, parents) == root(j, parents)
}

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