Go: package main

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

const (
	MAX_N      = 200
	MAX_WEIGHT = 2000
)

type Edge struct {
	start  int
	end    int
	weight int
}

type ShortestInfo struct {
	edges    []Edge
	shortest int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	shortestList := make([]ShortestInfo, n)
	for i := 1; i < n; i++ {
		shortestList[i] = ShortestInfo{edges: []Edge{}, shortest: MAX_N*MAX_WEIGHT + 1}
	}

	adjacentMatrix := make([][]int, n)
	for i := 0; i < n; i++ {
		adjacentMatrix[i] = make([]int, n)
		for j := 0; j < n; j++ {
			v, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			adjacentMatrix[i][j] = v
		}
	}

	mst([]int{1}, shortestList, adjacentMatrix)
	fmt.Println(calculateMinWeight(shortestList))
}

func calculateMinWeight(shortestList []ShortestInfo) int {
	visitedList := make([]bool, len(shortestList))
	visitedList[0] = true
	sumWeight := 0
	for !visitedAll(visitedList) {
		shortestInfo := shortestList[0]
		shortestList = shortestList[1:]
		edges := shortestInfo.edges
		for _, edge := range edges {
			if !visitedList[edge.end-1] {
				visitedList[edge.end-1] = true
				sumWeight += edge.weight
			}
		}
	}
	return sumWeight
}

func visitedAll(visitedList []bool) bool {
	for _, v := range visitedList {
		if !v {
			return false
		}
	}
	return true
}

func mst(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]int) {
	for len(nodeStack) > 0 {
		currentNode := nodeStack[0]
		nodeStack = nodeStack[1:]
		currentShortest := getShortest(currentNode, shortestList)
		adjacents := findAdjacents(currentNode, adjacentMatrix)
		for i := 0; i < len(adjacents); i++ {
			adj := adjacents[i]
			s := getShortest(adj.end, shortestList)
			if currentShortest.shortest+adj.weight < s.shortest || (currentShortest.shortest+adj.weight == s.shortest && len(currentShortest.edges)+1 > len(s.edges)) {
				setShortest(adj.end, adj, currentShortest, shortestList)
				nodeStack = append(nodeStack, adj.end)
			}
		}
	}
}

func getShortest(node int, shortestList []ShortestInfo) ShortestInfo {
	return shortestList[node-1]
}

func setShortest(node int, edge Edge, currentShortest ShortestInfo, shortestList []ShortestInfo) {
	newEdges := make([]Edge, len(currentShortest.edges)+1)
	for i := 0; i < len(newEdges)-1; i++ {
		newEdges[i] = currentShortest.edges[i]
	}
	newEdges[len(newEdges)-1] = edge
	shortestInfo := ShortestInfo{edges: newEdges, shortest: currentShortest.shortest + edge.weight}
	shortestList[node-1] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]int) []Edge {
	adjacents := adjacentMatrix[currentNode-1]
	edges := []Edge{}
	for i, v := range adjacents {
		if v > 0 {
			edges = append(edges, Edge{start: currentNode, end: i + 1, weight: v})
		}
	}
	return edges
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

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