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>
#define N 100
#define INFTY (1<<21)
#define WH 0
#define GR 1
#define BL 2
using namespace std;

vector<int> color(N),d(N),p(N);
vector<vector<int>> M(N,vector<int>(N));
int n;

int prim(){
	int u,mincost;
	for(int i=0;i<n;i++){
		color.at(i) = WH;
		d.at(i) = INFTY;
		p.at(i) = -1;
	}
	d.at(0) = 0;
	
	while(1){
		mincost = INFTY;
		u = -1;
		for(int i=0;i<n;i++){
			if(color.at(i) != BL && d.at(i) < mincost){
				mincost = d.at(i);
				u = i;
			}
		}
		if(u == -1) break;
		
		color.at(u) = BL;
		
		for(int v=0;v<n;v++){
			if(color.at(v) != BL && M.at(u).at(v) != INFTY){
				if(M.at(u).at(v) < d.at(v)){
					d.at(v) = M.at(u).at(v);
					p.at(v) = u;
					color.at(v) = GR;
				}
			}
		}
	}
	int sum=0;
	for(int i=0;i<n;i++){
		if(p.at(i) != -1) sum += M.at(i).at(p.at(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;
			if(e == -1) M.at(i).at(j) = INFTY;
			else M.at(i).at(j) = e;
		}
	}
	cout << prim() << 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 a, min;
   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 ) {
      min = INFTY;
      a = -1;
 
      for ( int i = 0; i < n; i++ ) {
         if ( min > d[i] && color[i] != BLACK ) {
            a = i;
            min = d[i];
         }
      }
 
      if ( a == -1 ) break;
      color[a] = BLACK;
      for ( int v = 0; v < n; v++ ) {
         if ( color[v] != BLACK && M[a][v] != INFTY ) {
            if ( d[v] > M[a][v] ) {
               d[v] = M[a][v];
               color[v] = GRAY;
            }
         }
      }
   }
 
   int sum = 0;
   for ( int i = 0; i < n; i++ ) {
      if ( p[i] != -1 ) sum = 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<iostream>
using namespace std;
#define MAX 100
#define INFTY 2001
#define WHITE 0
#define GRAY 1
#define BLACK 2

int M[MAX][MAX], d[MAX];

void prim(int n){
  int color[MAX], u;

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

  while(true){
    int mincost = INFTY;
    for(int i=0; i<n; i++){
      if(color[i] != BLACK && d[i] < mincost){
        mincost = d[i];
        u = i;
      }
    }

    if(mincost == INFTY) break;

    color[u] = BLACK;

    for(int v=0; v<n; v++){
      if(color[v] != BLACK && M[u][v] != INFTY){
        if(M[u][v] < d[v]){
          d[v] = M[u][v];
          //p[v] = u;
          color[v] = GRAY;
        }
      }
    }
  }
}

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

  prim(n);

  // 最小全域木の辺の重みの総和を計算
  int u = 0;
  int d_sum = 0;
  for(int i=0; i<n; i++){
    if(true){
      d_sum += d[i];
    }
  }
  cout << d_sum << endl;
  return 0;
}

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

#define N 105
int n;

int g[N][N];
int mini;
int weight[N];
bool us[N];

int prim(){
  int v;
  int ans=0;
  weight[1]=0;
  
  while(true){
    v=-1;
   
    for(int i=1;i<=n;i++){
      if(us[i]!=true && (v==-1 ||weight[i]<weight[v]))v=i;
    }

    if(v==-1)break;
    us[v]=true;
    ans+=weight[v];

    for(int i=1;i<=n;i++){
      if(weight[i]>g[v][i])weight[i]=g[v][i];
      else weight[i]=weight[i];
    }
  }
  return ans;
}


int main(){

  //load n
  cin >>n;

  //load data
  for(int i=1;i<=n;i++){
    weight[i]=1000;
    us[i]=false;
    for(int j=1;j<=n;j++){
      scanf("%d",&g[i][j]);
      if(g[i][j]== -1)g[i][j]=1000;
      //    cout <<g[i][j]<<" ";
    }
    //    cout <<endl;
  }




  //print
  cout <<prim()<<endl;

  return 0;

}

C++: #include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define REP(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
using namespace std;
typedef pair<int,int> PII;

int P[100]; //union_find

int root(int i){
    if(P[i] == i) return i;
    else return P[i] = root(P[i]);
}

bool same(int x, int y){
    return root(P[x]) == root(P[y]);
}

void unite(int x, int y){
    P[root(x)] = root(y);
}

int main(){
    int n;
    cin >> n;
    int g[n][n];
    vector<pair<int,PII> > V;
    REP(i,n){
        REP(j,n){
            cin >> g[i][j];
            if(i<j && g[i][j] >= 0) V.pb(mp(g[i][j],mp(i,j)));
        }
    }
    sort(all(V));
    REP(i,n){
        P[i] = i;
    }
    int wsum = 0, count = 0;
    REP(i,n*n){
        int x = V[i].snd.fst;
        int y = V[i].snd.snd;
        if(same(x,y)) continue;
        unite(x,y);
        wsum += V[i].fst;
        count++;
        if(count == n-1) break;
    }

    cout <<wsum<<endl;

    return 0;
}