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 <cstring>
using namespace std;
#define int long long

main(){
  int n;
  cin>>n;
  int a[n][n];
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      cin>>a[i][j];
  int ans=0;
  bool used[n];
  memset(used,0,sizeof(used));
  used[0]=1;
  int cost[n];
  for(int i=0;i<n;i++) cost[i]=a[0][i];
  while(1){
    int v=-1;
    for(int i=0;i<n;i++){
      if(used[i]||cost[i]<0) continue;
      if(v<0||cost[i]<cost[v]) v=i;
    }
    if(v<0) break;
    used[v]=1;
    ans+=cost[v];
    for(int i=0;i<n;i++){
      if(a[v][i]<0) continue;
      if(cost[i]<0||a[v][i]<cost[i]) cost[i]=a[v][i];
    }
  }
  cout<<ans<<endl;
}

C++: #include<iostream>
#include<list>
#include<vector>
const int INF = 2001;
using namespace std;
list<int> L;
bool ok(int i) {
    for (list<int>::iterator it = L.begin(); it != L.end(); it++) if (i == *it) return 0;
    return 1;
}
int main() {
    L.push_back(0);
    int n; cin >> n;
    int M[100][100];
    int tmp = INF;
    int id = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> M[i][j];
            if (i == 0 && M[i][j] != -1) {
                if (M[i][j] < tmp) {
                    tmp = M[i][j];
                    id = j;
                }
            }
        }
    }
    L.push_back(id);
    int ans = tmp;
    tmp = INF;
    int OK[100];
    while (1) {
        tmp = INF;
        for (int i = 0; i < n; i++) OK[i] = ok(i); //reached?
        for (list<int>::iterator it = L.begin(); it != L.end(); it++ ) { //from reached
            for (int i = 0; i < n; i++) {
                if (M[*it][i] < tmp && M[*it][i] != -1 && OK[i]) {
                    tmp = M[*it][i];
                    id = i;
                }
            }
        }
        if (tmp == INF) break;
        ans += tmp;
        L.push_back(id);
    }
    cout << ans << endl;
    return 0;
    
}