Go: package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

type ElementKey int
type Node struct {
	key    ElementKey
	parent *Node
	rank   int
}

func newNode(key ElementKey) *Node {
	node := Node{}
	node.key = key
	node.parent = &node
	node.rank = 0

	return &node
}

func union(x, y *Node) {
	xSet := findSet(x)
	ySet := findSet(y)
	link(xSet, ySet)
}

func link(x, y *Node) {
	if x.rank > y.rank {
		y.parent = x
	} else {
		x.parent = y

		if x.rank == y.rank {
			y.rank++
		}
	}
}

func findSet(x *Node) *Node {
	if x != x.parent {
		x.parent = findSet(x.parent)
	}
	return x.parent
}

func newDisjointSets(nSets int) *DisjointSets {
	sets := DisjointSets{}
	sets.keyToNode = map[ElementKey]*Node{}
	for i := 0; i < nSets; i++ {
		key := ElementKey(i)
		sets.keyToNode[key] = newNode(key)
	}
	return &sets
}

type DisjointSets struct {
	keyToNode map[ElementKey]*Node
}

func (sets *DisjointSets) union(x, y ElementKey) {
	xNode := sets.keyToNode[x]
	yNode := sets.keyToNode[y]
	union(xNode, yNode)
}

func (sets DisjointSets) findSet(x ElementKey) *Node {
	xNode := sets.keyToNode[x]
	return findSet(xNode)
}

type Edge struct {
	i, j   int
	weight int
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	sets := newDisjointSets(n)
	edges := []Edge{}
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, n)
		for j := 0; j < n; j++ {
			a[i][j] = nextInt()
			if a[i][j] >= 0 {
				e := Edge{
					i:      i,
					j:      j,
					weight: a[i][j],
				}
				edges = append(edges, e)
			}
		}
	}
	sort.Slice(edges, func(i, j int) bool { return edges[i].weight < edges[j].weight })
	totalWeight := 0
	for _, edge := range edges {
		i := ElementKey(edge.i)
		j := ElementKey(edge.j)
		if sets.findSet(i) != sets.findSet(j) {
			totalWeight += edge.weight
			sets.union(i, j)
		}
	}
	fmt.Println(totalWeight)
}

C++: #include <bits/stdc++.h>

using namespace std;
using LL = long long;
using P = pair<int, int>;
using Tapris = tuple<int, int, int>;

#define REP(i, n) for(LL i = 0; i < n; ++i)
#define FOR(i, a, n) for(LL i = a; i < n; ++i)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e15;
const int MOD = 1e9 + 7;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

//#define int long long

class UnionFind {
    private:
        vector<int> parent;  // 親
        vector<int> rank;    // 木の深さ
    public:
        UnionFind(int n);          // n要素で初期化
        int Find(int x);           // 木の根を返す
        void Unite(int x, int y);  // xとyの属する集合を併合
        bool Same(int x, int y);   // xとyが同じ集合に属するか否か
};

UnionFind::UnionFind(int n) : parent(vector<int>(n)), rank(vector<int>(n)) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

int UnionFind::Find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return parent[x] = Find(parent[x]);
    }
}

void UnionFind::Unite(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;

    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}

bool UnionFind::Same(int x, int y) { return Find(x) == Find(y); }

template <typename T>
struct Edge {
    int src, to;
    T cost;
    Edge(int to, T cost) : src(-1), to(to), cost(cost) {}
    Edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
};

template <typename T>
class Kruskal {
    private:
        int V; // 頂点数
        vector<Edge<T>> edges;
        vector<vector<Edge<T>>> minimumSpanningTree;
    public:
        Kruskal(int n);
        void AddEdge(int from, int to, T cost);
        T Run();
        vector<vector<Edge<T>>> GetMinimumSpanningTree();
};

template <typename T>
Kruskal<T>::Kruskal(int n) : V(n), minimumSpanningTree(n) {}

template <typename T>
void Kruskal<T>::AddEdge(int from, int to, T cost) {
    edges.push_back(Edge<T>(from, to, cost));
}

template <typename T>
T Kruskal<T>::Run() {
    sort(edges.begin(), edges.end(), [](const Edge<T> &a, const Edge<T> &b){
        return a.cost < b.cost;
    });
    UnionFind tree(V);
    T total = 0;
    
    for(auto &e : edges){
        if(!tree.Same(e.src, e.to)){
            tree.Unite(e.src, e.to);
            total += e.cost;
            minimumSpanningTree[e.src].push_back(Edge<T>(e.to, e.cost));
            minimumSpanningTree[e.to].push_back(Edge<T>(e.src, e.cost));
        }
    }

    return total;
}

template <typename T>
vector<vector<Edge<T>>> Kruskal<T>::GetMinimumSpanningTree(){
    return minimumSpanningTree;
}

/*************** using variables ***************/

/**********************************************/

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    Kruskal<int> kruskal(n);
    REP(i, n){
        REP(j, n){
            int x;
            cin >> x;
            if(x != -1) kruskal.AddEdge(i, j, x);
        }
    }

    cout << kruskal.Run() << endl;
}

C++: #include<bits/stdc++.h>
using namespace std;

struct Edge{
  int to,cost;
  bool operator<(const Edge&a)const{
    return cost>a.cost;
  }
};
struct Graph{
  Graph(int n):E(n),T(n),N(n){}
  vector<vector<Edge>>E,T;
  int N;
  void add_edge(int a,int b,int c){
    E[a].push_back({b,c});
    E[b].push_back({a,c});
  }
  void prim(int s){
    bool visited[N];
    priority_queue<pair<Edge,int>>Q;
    memset(visited,0,N);
    Q.push({{s,0},-1});
    while(!Q.empty()){
      Edge e=Q.top().first;
      int from=Q.top().second;Q.pop();
      if(visited[e.to])continue;
      visited[e.to]=1;
      if(from+1)T[from].push_back(e),T[e.to].push_back({from,e.cost});
      for(auto&a:E[e.to])
      if(!visited[a.to])Q.push({a,e.to});
    }
  }
  int get_cost(){
    int ret=0;
    for(auto&a:T)for(auto&b:a)ret+=b.cost;
    return ret/2;
  }
  vector<Edge>* get_MST(){
    return T.data();
  }
};

main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin>>N;
    Graph G(N);
    for(int i=0;i<N;++i)
        for(int j=0;j<N;++j){
            int a;
            cin>>a;
            if(~a) G.add_edge(i,j,a);
        }
    G.prim(0);
    cout<<G.get_cost()<<endl;
}

C++: #include <iostream>
using namespace std;
static const int MAX=100;
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;
static const int INF=1<<21;

int n;
int A[MAX][MAX];

int prim(){
  int i,color[MAX],d[MAX],p[MAX],mincost,k,sum;
  for(i=0;i<n;i++){
    color[i]=WHITE;
    d[i]=INF;
  }
  d[0]=0;
  p[0]=-1;

  while(1){
    mincost=INF;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && d[i]<mincost){
	mincost=d[i];
	k=i;
      }
    }
    if(mincost==INF) break;
    color[k]=BLACK;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && A[k][i]!=INF){
	if(A[k][i]<d[i]){
	  d[i]=A[k][i];
	  p[i]=k;
	  color[i]=GRAY;
	}
      }
    }
  }
  sum=0;
  for(i=0;i<n;i++){
    if(p[i]!=-1){
      sum+=A[i][p[i]];
    }
  }
  return sum;
}

int main(){
  int i,j,a;
  cin>>n;

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      cin>>a;
      if(a!=-1){
	A[i][j]=a;
      }
      else A[i][j]=INF;
    }
  }

  cout<<prim()<<endl;

  return 0;
}