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 <utility>
#include <algorithm>
#include <iostream>
using namespace std;


// ????????????union-find tree
int P[10010];
void init(int N){
  for(int i=0; i<=N; i++){
    P[i] = i;
  }
}

int root(int a) {
  if(P[a]==a)return a; // a???root
  return (P[a] = root(P[a])); // a?????????root????±????, a????????¨??????
}
bool is_same_set(int a, int b){ // a??¨b???????????°?????????????±?????????????
  return root(a) == root(b);
}
void unite(int a, int b){ // a??¨b???????????°?????????????????¨??????
  P[root(a)] = root(b);
}
// ???????????§???union-find tree


int main(){
  int n;
  cin >> n;
  pair<int,int> E[1000010];
  int a;
  int k=0;
  int m=0;
  int S[10010], G[10010];
  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      cin >> a;
      E[k].first = a; // ????????????
      E[k].second = m; // ????????????
      S[m] = i;
      G[m] = j;
      k++;
      m++;
      
    }
  }
    
#if 0
  for(int i=0; i<n*n; i++){
    cout << E[i].first << " " << E[i].second;
    cout << " -> " << S[E[i].second] << " " << G[E[i].second] << endl;
  }
#endif


  sort(E, E+n*n);

#if 0
  cout << endl;
  for(int i=0; i<n*n; i++){
    cout << E[i].first << " " << E[i].second;
    cout << " -> " << S[E[i].second] << " " << G[E[i].second] << endl;
  }
#endif
  
  
  int T = 0; // ?£?T????????????
  init(n); // ??¢??°??????, ?????°??????????????°

  for(int i=0; i<n*n; i++){
    if(E[i].first!=-1){
      if(is_same_set(S[E[i].second],G[E[i].second])==0){
	T += E[i].first;
	unite(S[E[i].second],G[E[i].second]);
      }
    }
    
  }

  cout << T << endl;
}

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

static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

int prim()
{
  int u, minv=0;
  int d[MAX], p[MAX], color[MAX];

  for (int i = 0; i < n; i++ )
  {
    d[i] = INFTY;
    p[i] = -1;
    color[i] = WHITE;
  }

  d[0] = 0;

  while ( 1 )
  {
    minv = INFTY;
    u = -1;
    for ( int i = 0; i < n; i++ )
    {
      if ( minv > d[i] && color[i] != BLACK )
      {
        u = i;
        minv = d[i];
      }
    }
    if (u == -1) break;
    color [u] = BLACK;
    for (int k = 0; k < n; k++ )
    {
      if ( color[k] != BLACK && M[u][k] != INFTY )
      {
        if( d[k] > M[u][k] )
        {
          d[k]=M[u][k];
          p[k]=u;
          color[k] = GRAY;
        }
      }
    }
  }
  int sum = 0;
  for ( int i = 0; i< n; i++ )
  {
    if ( p[i] != -1 ) sum += M[i][p[i]];
  }
  return sum;
}

int main()
{
  cin >> n;
  for ( int i = 0; i < n; i++ )
  {
    for ( int j = 0; j < n; j++ )
    {
      int e; cin >> e;
      M[i][j] = (e == -1) ? INFTY : e;
    }
  }
  cout << prim() << endl;
  return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define PI 3.14159265358979323846
#define vll vector<long long>
using namespace std;
using ll = long long;
using ld = long double;

// -------------------------------------------------
class UnionFind {
private:
  ll n;
  vll P;
  ll root(ll x);
  void setN(ll N);
  void init();

public:
  UnionFind(ll N);
  void unite(ll x, ll y);
  bool same(ll x, ll y);
};

// コンストラクタ
UnionFind::UnionFind(ll N) {
  setN(N);
  init();
}

// nを変更
void UnionFind::setN(ll N) { n = N; }

// Union-Find Treeを初期化する
void UnionFind::init() {
  P.clear();
  rep(i, n) { P.push_back(i); }
}

// 根の値を返す
ll UnionFind::root(ll x) {
  if (P[x] == x) { return x; }
  return (P[x] = root(P[x])); // パス圧縮しつつ返す
}

// 木を結合する（rankはとりあえず無視）
void UnionFind::unite(ll x, ll y) { P[root(x)] = root(y); }

// xとyが同じ集合にあるか判別
bool UnionFind::same(ll x, ll y) {
  if (root(x) == root(y)) {
    return true;
  } else {
    return false;
  }
}
// -------------------------------------------------

// ----本問について----
// 問題：最小全域木
// 問題文URL：https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_12_A
// 所要時間：
// 学んだこと：
// ------------------

// ----ここから本問のソースコード----

struct edge {
  ll w, s, e; // weight, start, end

  edge(ll W, ll S, ll E) {
    w = W;
    s = S;
    e = E;
  }
};

bool cmpI(const edge &a, const edge &b) { return a.w < b.w; }

// グローバル変数（入力）
ll n;
vector<vll> A;

// 隣接行列から辺の情報を取り出す
vector<edge> MakeEdges() {
  vector<edge> edges;
  rep(i, n) {
    for (ll j = i + 1; j < n; j++) {
      if (A[i][j] != -1) { edges.push_back(edge(A[i][j], i, j)); }
    }
  }
  return edges;
}

// 入力
void input() {
  cin >> n;
  rep(i, n) {
    vll a(n);
    rep(j, n) { cin >> a[j]; }
    A.push_back(a);
  }
}

// 最小全域木の重みの合計を求める（クラスカル法）．
void solve() {
  vector<edge> edges = MakeEdges();
  // 辺を重みをキーに昇順ソート
  sort(edges.begin(), edges.end(), cmpI);
  UnionFind u(n);
  ll ans = 0;
  rep(i, edges.size()) {
    if (!u.same(edges[i].s, edges[i].e)) { // 閉路ができない
      u.unite(edges[i].s, edges[i].e);
      ans += edges[i].w;
    }
  }
  cout << ans << endl;
}

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

C++: #include <queue>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	vector<vector<short>> dist(n, vector<short>(n));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			scanf("%hd", &dist[i][j]);
			dist[i][j] = dist[i][j] < 0 ? 10000 : dist[i][j];
		}
	}
	
	vector<bool> visited(n, false);
	priority_queue<pair<short,int>, vector<pair<short,int>>, greater<pair<short,int>>> q;
	q.push(make_pair(0, 0));
	
	int ans = 0;
	while(q.size()){
		pair<short,int> edge = q.top();
		q.pop();
		if(visited[edge.second]) continue;
		ans += edge.first;
		visited[edge.second] = true;
		for(int i = 0; i < n; i++){
			if(!visited[i]){
				q.push(make_pair(dist[i][edge.second], i));
			}
		}
	}
	
	printf("%d\n", ans);
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef	tuple<int,int,int>T;
typedef vector<T>VT;
int main(void){
	int n;
	int box[101][101];
	int i,j;
	int per[101];
	int ran[101];
	int x,y;
	int sum;
	VT v;
	cin>>n;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			cin>>box[i][j];
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(box[i][j]!=-1){
				v.push_back(make_tuple(box[i][j],i,j));
			}
		}
	}
	sort(v.begin(),v.end());
	for(i=1;i<=n;i++){
		per[i]=i;
		ran[i]=1;
	}
	sum=0;
	for(i=0;i<v.size();i++){
		x=get<1>(v[i]);
		y=get<2>(v[i]);
		while(x!=per[x])	x=per[x];
		while(y!=per[y])	y=per[y];
		if(x!=y){
			sum+=get<0>(v[i]);
			if(ran[x]>ran[y])		per[y]=x;
			else if(ran[x]<ran[y])	per[x]=y;
			else{
				per[x]=y;
				ran[x]++;
			}
		}
	}
	cout<<sum<<endl;
	return 0;
}