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 <iostream>
#include <algorithm>
#include <vector>
#include<string>
#include <set>
#include <map>
#include <queue>
#include <limits.h>
#include <cmath>

using namespace std;

#define rip(i,n,s) for (int i=(s);i<(int)(n);i++)
#define all(a) (a).begin(),(a).end()
typedef long long ll;

struct UnionFind{
    int size;
    vector<int> par;
    vector<int> rank;
    UnionFind(int x){
        size=x;
        par=vector<int> (x);
        rank=vector<int> (x,1);
        for (int i=0;i<x;i++){
            par[i]=i;
        }
    }
    int root(int x){
        if(par[x]==x){
            return x;
        }
        else{
            return par[x]=root(par[x]);
        }
    }
    void unite(int x,int y){
        x=root(x);y=root(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 check(int x,int y){
        return root(x)==root(y);
    }
    void initialize(){
        for (int i=0;i<size;i++){
            par[i]=i;
        }
    }
};

typedef pair<int,pair<int,int>> P;

int main(){
    int n;
    cin >> n;
    UnionFind uf(n);
    priority_queue<P,vector<P>,greater<P>> q;
    int v;
    P now;
    rip(i,n,0){
        rip(j,n,0){
            cin >> v;
            if(v>=0 && i>j){
                now.first=v;
                now.second.first=i;
                now.second.second=j;
                q.push(now);
            }
        }
    }
    int co=n-1;
    int ans=0;
    while (co){
        now=q.top();
        q.pop();
        if(uf.check(now.second.first,now.second.second)){
            continue;
        }
        ans+=now.first;
        uf.unite(now.second.first,now.second.second);
        co--;
    }
    printf("%d\n",ans);
}

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

static const int MAX = 100;
static const int INF = (1<<30);
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,ii,vv;
  int d[MAX],p[MAX],color[MAX];

  //cout << "prim" << endl;
  //条件初期化
  for(ii=0;ii<n;ii++){
    d[ii] = INF;
    p[ii] = -1;
    color[ii] = WHITE;
  }

  d[0] = 0;

  while(1){

    minv = INF;
    u = -1;

    //起点の決定
    for(ii=0;ii<n;ii++){
      if(minv > d[ii] && color[ii] != BLACK){
        //cout << "ii:" << ii << endl;
        u = ii;
        minv = d[ii];
      }
    }

    if(u == -1){
      break;
    }

    //起点を探索済みに
    color[u] = BLACK;

    for(vv=0;vv<n;vv++){
      //未探索かつパスの繋っている位置
      if(color[vv] != BLACK && M[u][vv] != INF){
        if( d[vv] > M[u][vv]){
          d[vv] = M[u][vv];
          p[vv] = u;
          color[vv] = GRAY;
        }
      }
    }
  }

  int sum = 0;
  for(ii=0;ii<n;ii++){
    if(p[ii] != -1){
      sum += M[ii][p[ii]];
    }
  }
  
  return sum;
  
}

int main(){
  cin >> n;
  int ii,jj;

  for(ii=0;ii<n;ii++){
    for(jj=0;jj<n;jj++){
      int cost;
      cin >> cost;

      if(cost == -1){
        M[ii][jj] = INF;
      }
      else{
        M[ii][jj] = cost;
      }
    }
  }

  cout << prim() << endl;
  
}

C++: #include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
#define FOR(i,a,b)   for(ll i = (a); i < (b); i++ )
#define REP(i, n)    FOR(i,0,n)
typedef pair< int, int >   cp2;
typedef pair< int, cp2 >   cp3;
#define fi first
#define se second
#define sec  se.fi
#define thr  se.se
const ll mod = 1000000007;
//              123456789


 

///////////////////////////////////////////////
//
//
///////////////////////////////////////////////

////////////////////////////////////////////////
////////////////////////////////////////////////



priority_queue< cp3, vector<cp3>, greater<cp3> >p;
cp3 now;

int g[112];

int find( int key ){
	//cout<<key<<" "<<g[key]<<endl;
	if( g[key] < 0 ) return key;
	return g[key] = find( g[key] );
}

void unite( int x, int y ){
	x = find( x );
	y = find( y );
	if( x == y ) return;
	
	if( g[x] < g[y] ) swap( x, y );
	if( g[x] == g[y] ) g[y]--;//??±??????x???????????????
	//g[y] += g[x];		 //????????°???x??????????°???????
	g[x] = y;
}

int a[112][112];
int N;
int ans = 0;

int main(){
	
	cin>>N;
	
	fill( g, g+112, -1 );
	
	
	REP( i, N ){
		REP( j, N ){
			scanf("%d",&a[i][j]);
			if( a[i][j] != -1 ){
				p.push( cp3( a[i][j], cp2(i, j) ) );
				//printf("%d %d %d\n",p[idx].fi, p[idx].sec, p[idx].thr);
				
			}
		}
	}
	
	while( !p.empty() ){
		now = p.top();
		p.pop();
		
		if( find(now.sec) != find(now.thr) ){
			unite( now.sec, now.thr );
			ans += now.fi;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;

}

C++: #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int G[MAX][MAX];
int color[MAX], d[MAX], p[MAX];
int n;

int prim();

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> G[i][j];
            if(G[i][j] == -1) G[i][j] = INT_MAX;
        }
    }

    cout << prim() << endl;

    // for(int i = 0; i < n; i++){
    //     cout << i << " " << p[i] << endl;
    // }

    return 0;
}

int prim(){
    // プリムのアルゴリズム
    // 重み付きグラフから最小全域木を求め、その辺の重みの合計を求める
    // colorは訪問状態を表す　
    // d[i]は頂点iから繋がる辺の内最小のもの　
    // p[i]は頂点iの親（木なので）
    for(int i = 0; i < n; i++){
        color[i] = WHITE;
        d[i] = INT_MAX;
        p[i] = -1;
    }
    
    d[0] = 0;

    while(1){
        int min = INT_MAX, u = -1;
        
        // 隣接する最小の辺を持つところに行く 頂点番号u 辺のおもみmin
        for(int i = 0; i < n; i++){
            if(d[i] < min && color[i] != BLACK){
                min = d[i];
                u = i;
            }
        }

        // 隣接するところが全てblack、または最小のものが存在しない時は探索終了
        if(u == -1) break;

        // 頂点番号uのところに訪問
        color[u] = BLACK;

        // uから繋がるところでまだ訪問してないところの内、最小のものを見つける
        for(int i = 0 ; i < n; i++){
            if(color[i] != BLACK && G[u][i] != INT_MAX){
                if(d[i] > G[u][i]){
                    d[i] = G[u][i];
                    p[i] = u;
                    color[i] = GRAY;
                }
            }
        }
    }

    int sum = 0;
    for(int i = 0; i < n; i++){
        if(p[i] != -1) sum += G[i][p[i]];
    }

    return sum;
}