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 <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// =======================
// ------ graph ------ //
using Weight = int;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) { }
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight < f.weight :
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge1(Graph &g, int a, int b, Weight w = 1) {
    g[a].emplace_back(a, b, w);
}

// ------ disjoint set ------ //
struct UnionFind {
    vector<int> data;
    int __size;
    UnionFind(int size) : data(size, -1), __size(size) { }
    bool unionSet(int x, int y) {
        if ((x = root(x)) != (y = root(y))) {
            if (data[y] < data[x]) swap(x, y);  // par -> child とは限らない
            data[x] += data[y]; data[y] = x; __size--;
        }
        return x != y;
    }
    bool findSet(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
    int size() { return __size; }
    vector<int> subset_roots() {
        vector<int> roots;
        for (int i = 0; i < data.size(); i++) if (data[i] < 0) roots.push_back(i);
        return roots;
    }
};

// ------ kruskal ------ //
pair<Weight, Edges> kruskal(const Graph &g) {
    UnionFind uf(g.size());
    Edges es;
    for (auto &adj : g) for (auto &e : adj) es.emplace_back(e);
    sort(es.begin(), es.end());
    Weight total = 0;
    Edges T;
    for (auto &e : es) if (uf.unionSet(e.src, e.dst)) {
        T.push_back(e);
        total += e.weight;
    }
    return make_pair(total, T);
}
// =======================

int main() {
    int n; cin >> n;
    Graph G(n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        int w; cin >> w;
        if (w >= 0) add_edge1(G, i, j, w);
    }
    pair<Weight, Edges> res = kruskal(G);
    cout << res.first << endl;
    return 0;
}

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

const int MAX = 100;

int count(bool check[MAX], int graph[MAX][MAX], int n,int i) {
	check[i] = true;
	int sum = 0;
	for (int j = 0; j < n; j++) {
		if (graph[i][j] != -1 && check[j] == false) {
			sum += count(check,graph, n, j);
			sum += graph[i][j];
		}
	}
	return sum;
}

int main() {
	int n;
	int g;
	int graph[MAX][MAX];

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
		}
	}

	//?????±???
	for (int m = 0; m < n; m++) {
		//?§????
		for (int b = 0; b < n; b++) {
			if (graph[b][m] == -1)continue;
			//??????
			for (int e = 0; e < n; e++) {
				if (graph[m][e] == -1 || graph[b][e] == -1)continue;
				if (graph[b][e] >= graph[b][m] + graph[m][e]) {
					graph[b][e] = -1;
				}
			}
		}
	}

	bool check[MAX] = { false };
	cout << count(check, graph, n, 0) << endl;
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

void solve(){
  int n; cin >> n;
  vector<vector<int> > v(n, vector<int>(n));
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin >> v[i][j];
    }
  }
  vector<int> t, c(n);
  t.push_back(0);
  c[0] = 1;
  int ans = 0;
  while(t.size() != n){
    int mini, minj, mint = 100000;
    for(int i = 0; i < t.size(); i++){
      for(int j = 0; j < n; j++){
        if(v[t[i]][j] >= 0 && c[j] == 0){
          if(v[t[i]][j] < mint){
            mini = i;
            minj = j;
            mint = v[t[i]][j];
          }
        }
      }
    }
    ans += mint;
    t.push_back(minj);
    c[minj] = 1;
  }
  cout << ans << endl;
  return;
}

int main(){
  solve();
  return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;

static const int INFTY = (1<<21);
enum Color{
    WHITE,
    GRAY,
    BLACK
};
int n;

int M[100][100];
Color color[100];
int d[100];
int q[100];

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

    while(true){
        int minv = INFTY;
        int 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]!=INFTY){
                if(d[v]>M[u][v]){
                    d[v] = M[u][v];
                    q[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    int sum = 0;
    for(int i=0; i<n; i++){
        if(q[i]!=-1) sum+=M[i][q[i]];
    }
    return sum;
}

int main(){

    scanf("%d", &n);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int x;
            scanf("%d", &x);
            if(x==-1) M[i][j] = INFTY;
            else M[i][j] = x;
        }
    }
    int x = prim();

    printf("%d\n", x);

    return 0;
}

C++: 
#include<stdio.h>

#define MAX 100
#define INFINITY 10000

int n;
int M[MAX][MAX], color[MAX], d[MAX], p[0];

enum {
    WHITE,
    GRAY,
    BLACK
};

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

    while (true) {
        int min = INFINITY;
        int target = -1;
        for (int i = 0; i < n; ++i) {
            if (d[i] < min && color[i] != BLACK) {
                min = d[i];
                target = i;
            }
        }
        if (target == -1) break;

        color[target] = BLACK;

        for (int v = 0; v < n; ++v) {
            if (color[v] != BLACK && M[target][v] > 0) {
                if(M[target][v] < d[v]) {
                    d[v] = M[target][v];
                    p[v] = target;
                    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() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &M[i][j]);
        }
    }
    printf("%d\n", prim());
    return 0;
}