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
	for len(edges) > 0 {
		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
	}
	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>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvd = vector<vd>;
using vvvi = vector<vvi>;
using vvvll = vector<vvll>;
using vvvd = vector<vvd>;

const double pi=acos(-1);
const ll MOD=1e9+7;
const ll INF=(1LL<<60);

int cost[101][101];
int mincost[101];
int used[101];
int v;

int prim(){
    for (int i=0;i<v;i++){
        mincost[i]=1e9;
        used[i]=0;
    }
    mincost[0]=0;
    int res=0;
    while(1){
        int v1=-1;
        for (int u=0;u<v;u++){
            if (!used[u] && (v1==-1||mincost[u]<mincost[v1]))v1=u;
        }
        if (v1==-1)break;
        used[v1]=1;
        res+=mincost[v1];
        for (int u=0;u<v;u++)mincost[u]=min(mincost[u],cost[v1][u]);
    }
    return res;
}

int main() {
    cin>>v;
    rep(i,v){
        rep(j,v){
            cin>>cost[i][j];
            if (cost[i][j]==-1)cost[i][j]=1e8;
        }
    }
    int ans=0;
    ans=prim();
    cout<<ans<<endl;
    

    return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1 << 28;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

const int MAX = 100;
const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;

int n, M[MAX][MAX];

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

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

	d[0] = 0;

	while (1) {
		minv = INF;
		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 v = 0; v < n; v++) {
			if (color[v] != BLACK && M[u][v] != INF) {
				if (d[v] > M[u][v]) {
					d[v] = M[u][v];
					p[v] = u;
					color[v] = 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) ? INF : e;
		}
	}

	cout << prim() << endl;

	return 0;
}

C++: #include <iostream>
#include <vector>
#include <queue>
#define to first
#define cost second
const int inf=1e9+7;
using namespace std;
int main(){

  int n,tmp,r=0,flag[100]={},v=0;
  cin>>n;
  vector <pair<int,int> > gl[n];
  priority_queue <pair<int,int> ,vector<pair<int,int> >, greater<pair<int,int> > >q;
  //for(int i=1;i<n;i++) mincost[i]=inf;                                                                                                                                                       

  for(int i=0;i<n;i++) for(int j=0;j<n&&cin>>tmp;j++) if(tmp!=-1) gl[i].push_back(make_pair(j,tmp));
  int now=0;
  for(int j=0;j<n-1;j++){
    for(int i=0;i<gl[now].size();i++) if(!flag[gl[now][i].to]) q.push(make_pair(gl[now][i].cost,gl[now][i].to));
    flag[now]=1;
    for(;flag[q.top().second];) q.pop();
    //if(q.empty()) break;                                                                                                                                                                     
    r+=q.top().first;
    now=q.top().second;
    q.pop();
  }
  cout<<r<<endl;
  return 0;

}

C++: #include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
using namespace std;

int main(){
	
	int n;
	cin>>n;
	vector<vector<int>> a(n);
	rep(i,n){
		a[i].resize(n);
		rep(j,n){
			cin>>a[i][j];
			if(a[i][j]==-1)a[i][j]=INF;
		}
	}
	vector<int> t(n);
	rep(i,n){
		t[i]=0;
	}
	t[0]=1;
	int ans=0;
	rep(ii,n-1){
		int m=100000;
		int pm;
		rep(i,n){
			rep(j,n){
				if(t[i]==1 && t[j]==0 && m>a[i][j]){
					m=a[i][j];
					pm=j;
				}
			}
		}
		t[pm]=1;
		ans+=m;
	}
	cout<<ans<<endl;
	
}

C++: #include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
#define pb push_back
#define int long long
#define MAX 100
#define NIL -1
using namespace std;
const int INF=1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int M[102][102];
int mincos[102];
bool used[102];
int n;

int prim(){
  rep(i,n){
    mincos[i]=INF;
    used[i]=false;
  }
  mincos[0]=0;
  int sum=0;
  while(1){
    int  v=-1;
    rep(i,n){
      if(used[i]==false&&(v==-1||mincos[i]<mincos[v]))v=i;
    }
    if(v==-1)break;
    used[v]=true;
    sum+=mincos[v];
    rep(i,n)mincos[i]=min(mincos[i],M[v][i]);
  }
  return sum;
}

signed main(){
  cin>>n;
  rep(i,n)rep(j,n){
    int e;
    cin>>e;
    M[i][j]=(e==-1?INF:e);
  }
  cout<<prim()<<endl;

  return 0;
}

C++: #include <iostream>
#include <algorithm>

using namespace std;

#define MAX_V 100
#define MAX_E 10000

int par[MAX_V],rank[MAX_V];
int V,E;

struct edge{ int u,v,cost; };
edge es[MAX_E];

bool comp(const edge &e1, const edge &e2){
  return e1.cost < e2.cost;
}

void init(int n){
  for(int i = 0 ; i < n ; i++){
    par[i] = i;
    rank[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(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 same(int x,int y){
  return find(x) == find(y);
}

int kruskal(){
  sort(es, es + E, comp);

  init(V);
  int res = 0;

  for(int i = 0 ; i < E ; i++){
    edge e = es[i];

    if(!same(e.u,e.v)){
      unite(e.u,e.v);
      res += e.cost;
    }
  }
  return res;
}

int main(){
  int c;

  cin >> V;
  for(int i = 0 ; i < V ; i++){
    for(int j = 0 ; j < V ; j++){
      cin >> c;

      if(c == -1){
	continue;
      }

      edge e = {i,j,c};
      es[E++] = e;
    }
  }

  cout << kruskal() << endl; 

  return 0;
}