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 <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

class UnionFind {
public:
  int N;
  int* root;
  int* rank;

  UnionFind(int n) : N(n) {
    root = new int[N];
    rank = new int[N];
    for (auto i = 0; i < N; ++i) {
      root[i] = i;
      rank[i] = 0;
    }
  }

  ~UnionFind() {
    delete[] root;
    delete[] rank;
  }

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

  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) {
      root[x] = y;
    } else {
      root[y] = x;
      if (rank[x] == rank[y]) ++(rank[x]);
    }
  }

  bool same(int x, int y) {
    return (find(x) == find(y));
  }
};

class Edge {
public:
  int src, dst, cost;
  Edge(int s, int d, int c)
    : src(s), dst(d), cost(c) {}
  friend bool operator<(const Edge& x, const Edge& y) {
    return x.cost < y.cost;
  }
};

typedef Edge State;

class Graph {
public:
  int N;
  vector<Edge>* V;
  vector<Edge> W;
  // dfs, bfs
  int* visited;
  int* from;
  int time;
  int* time_d;
  int* time_f; // dfs
  int* dist;
  int* root;
  // kruskal
  int kruskal_cost;
  vector<Edge>* kruskal_V;
  vector<Edge> kruskal_W;

  Graph(int n)
    : N(n), time(0), kruskal_cost(-1) {
    V = new vector<Edge>[N];
    from = new int[N];
    time_d = new int[N];
    time_f = new int[N];
    visited = new int[N];
    fill(visited, visited+N, 0);
    dist = new int[N];
    root = new int[N];
    kruskal_V = new vector<Edge>[N];
  }
  ~Graph() {
    delete[] V;
    delete[] from;
    delete[] time_d;
    delete[] time_f;
    delete[] visited;
    delete[] dist;
    delete[] root;
    delete[] kruskal_V;
  }

  void add_edge(int src, int dst, int cost = 1) {
    Edge e(src, dst, cost);
    V[src].push_back(e);
    W.push_back(e);
  }

  bool is_connected(int s, int t) {
    if (visited[s] == 0) {
      dfs(s);
    }
    if (visited[t] == 0) {
      dfs(t);
    }
    return (root[s] == root[t]);
  }

  void dfs(int start) {
    stack<State> S;
    S.push(State(-1, start, 0));
    while (!S.empty()) {
      State s = S.top();
      S.pop();
      if (visited[s.dst] == 0) {
        visited[s.dst] = 1;
        time_d[s.dst] = time++;
        from[s.dst] = s.src;
        dist[s.dst] = s.cost;
        root[s.dst] = start;
        S.push(s);
        for (auto x : V[s.dst]) {
          if (visited[x.dst] == 0) {
            S.push(State(s.dst, x.dst, s.cost + x.cost));
          }
        }
      } else if (visited[s.dst] == 1) {
        visited[s.dst] = 2;
        time_f[s.dst] = time++;
      }
    }
  }

  void bfs(vector<int> start) {
    assert(!start.empty());
    queue<State> Q;
    for (auto x : start) {
      Q.push(State(-1, x, 0));
    }
    while (!Q.empty()) {
      State s = Q.front();
      Q.pop();
      if (visited[s.dst] == 0) {
        visited[s.dst] = 1;
        time_d[s.dst] = time++;
        from[s.dst] = s.src;
        dist[s.dst] = s.cost;
        root[s.dst] = start[0];
        for (auto x : V[s.dst]) {
          if (visited[x.dst] == 0) {
            Q.push(State(s.dst, x.dst, s.cost + x.cost));
          }
        }
      }
    }
  }

  int kruskal() {
    if (kruskal_cost != -1) return kruskal_cost;
    sort(W.begin(), W.end());
    UnionFind u(N);
    int kruskal_cost = 0;
    for (auto e : W) {
      if (!u.same(e.src, e.dst)) {
        kruskal_V[e.src].push_back(e);
        kruskal_W.push_back(e);
        u.unite(e.src, e.dst);
        kruskal_cost += e.cost;
      }
    }
    return kruskal_cost;
  }
};

int main () {
  int n;
  cin >> n;
  Graph g(n);
  for (auto i = 0; i < n; ++i) {
    for (auto j = 0; j < n; ++j) {
      int a;
      cin >> a;
      if (a != -1) {
        g.add_edge(i, j, a);
      }
    }
  }
  cout << g.kruskal() << endl;
}

C++: #include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;

constexpr int LEN = 105;
int a[LEN][LEN];

int prim(int n){
	bool check[n];
	int p[n], d[n];
	memset(check, 0, n*sizeof(bool));
	memset(p, -1, n*sizeof(int));
	memset(d, 1, n*sizeof(int));
	rep(i, n) p[i] = INT_MAX;
	d[0] = 0;
	p[0] = -1;

	while(true){
		int min_cost = INT_MAX;
		int now_v;
		rep(i, n){
			if(!check[i] && d[i] < min_cost){
				min_cost = d[i];
				now_v = i;
			}
		}
		if(min_cost == INT_MAX) break;

		check[now_v] = true;

		rep(v, n){
			if(!check[v] && (a[now_v][v] > -1) && (a[now_v][v] < d[v])){
				d[v] = a[now_v][v];
				p[v] = now_v;
			}
		}
	}

	int sum = 0;
	rep(i, n) sum += d[i];

	return sum;
}

int main(){
	int n; cin >> n;
	rep(i, n)rep(j, n) {
		int w; cin >> w;
		a[i][j] = w;
		a[j][i] = w;
	}

	cout << prim(n) << endl;

	return 0;
}

C++: //Minimum Spannig Tree
#include <iostream>
#include <climits>

using namespace std;

static const int N = 100;
static const int WHITE = 0;
static const int BLACK = 1;
int n, A[N][N], colors[N], d[N], p[N];

int prim() {
    int l = 0, mincost, u;
    for(int i = 0; i < N; i++) {
        colors[i] = WHITE;
        d[i] = INT_MAX;
    }
    d[0] = 0;
    p[0] = -1;
    while(1) {
        mincost = INT_MAX;
        for(int i = 0; i < n; i++) {
            if(colors[i] == WHITE && d[i] < mincost) {
                mincost = d[i];
                u = i;
            }
        }
        if(mincost == INT_MAX) break;
        colors[u] = BLACK;
        l += mincost;
        for(int v = 0; v < n; v++) {
            if(colors[v] == WHITE && A[u][v] != -1) {
                if(A[u][v] < d[v]) {
                    d[v] = A[u][v];
                    p[v] = u;
                }
            }
        }
    }
    return l;
}

int main() {
    int a;
    cin >> n;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) A[i][j] = -1;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++){
            cin >> a;
            A[i][j] = a;
        }
    }
    cout << prim() << endl;
}