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 <algorithm>
#define N 100
#define INF 2000000000
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;

int n;
int M[N][N],color[N],d[N],p[N];
   //M??????????????????color????¨??????¶???(0,1,2),d????????????????°???????????¨????
   //p???MST???????°???¨?????¨??????????????????????????????

void Prim() {
	for (int i = 0;i < n;i++) d[i] = INF;
	d[0] = 0;  //?????????????????????????????§???????????§????´???????????????????????????????
	/*p[0] = -1;  //??????????????????????????????????????????*/

	int u;
	while (true) {
		int min = INF;
		for (int i = 0;i < n;i++) {
			if(color[i]!=BLACK&&min>d[i]){
				min = d[i];
				u = i;
			}
		}

	if (min == INF) break;

	color[u] = BLACK;

	for (int v = 0;v < n;v++) 
		if(color[v]!=BLACK&&M[u][v]!=-1)
			if (M[u][v] < d[v]) {
				d[v] = M[u][v];
				/*p[v] = u;*/
				/*color[v] = GRAY;*/
			}

	}

	int sum = 0;
	for (int i = 0;i < n;i++) sum += d[i];
	cout << sum << endl;
		
}

int main() {
	cin >> n;
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++) {
			cin >> M[i][j];
			if (M[i][j] == -1) M[i][j] = INF;
		}

	Prim();

}

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

#define _CRT_SECURE_NO_WARNINGS

#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)
#define REP3(i, x, n) for(decltype(x) i = (x); i <= (n); i++)
#define RREP(i, n) for (decltype(n) i = (n) - 1; i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

const int INF = 1000000000;
const double PI = 3.1415926535897932384626433832795;

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

using LL = long long int;
using LD = long double;
using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vl = vector<LL>;
using vd = vector<double>;
using vs = vector<string>;
using vvi = vector<vi>;

//==============================================
int n;
vi color, D, P;
vvi M;

int solve() {
	D[0] = 0;

	int u, minV;
	while (true) {
		u = -1;
		minV = INF;
		REP(i, n) {
			if (color[i] != 2 && D[i] < minV) {
				u = i;
				minV = D[i];
			}
		}

		if (u == -1) break;
		color[u] = 2;

		REP(i, n) {
			if (color[i] != 2 && M[u][i] != INF && D[i] > M[u][i]) {
				D[i] = M[u][i];
				P[i] = u;
				color[i] == 1;
			}
		}
	}

	int sum = 0;
	REP(i, n) {
		if (P[i] != -1) {
			sum += M[i][P[i]];
		}
	}

	return sum;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;

	color.resize(n);
	D.resize(n, INF);
	P.resize(n, -1);
	M.resize(n, vi(n, INF));

	int edge;
	REP(i, n) {
		REP(j, n) {
			cin >> edge;
			M[i][j] = (edge == -1 ? INF : edge);
		}
	}

	cout << solve() << "\n";
	return 0;
}

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

int main() {
	int num;
	std::cin >> num;

	std::vector<std::vector<int> > v(num);

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			int n;
			std::cin >> n;
			v[i].push_back(n);
		}
	}

	std::vector<int> n(v.size(), 0);
	int count = 0;
	for (int i = 1; i <= 2000; i++) {
		for (size_t j = 0; j < v.size(); j++) {
			for (size_t k = 0; k < v.size(); k++) {
				if (v[j][k] == i && (n[j] == 0 || n[k] == 0)) {
					n[j] = n[k] = 1;
					count += i;
				}
			}
		}
	}

	std::cout << count << std::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 s = 0; s < n; s++) {
		//?????±???
		for (int m = 0; m < n; m++) {
			if (graph[s][m] == -1)continue;
			//??????
			for (int e = 0; e < n; e++) {
				if (graph[s][e] == -1 || graph[m][e] == -1)continue;
				if (graph[s][e] > graph[s][m] + graph[m][e]) {
					graph[s][e] = -1;
				}
			}
		}
	}

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

C++: #include <iostream>
using namespace std;
const int INF = 1e9 + 7;
const int MAX_V = 100;

int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];
int V;

int prim() {
    for (int i = 0; i < V; ++i) {
        mincost[i] = INF;
        used[i] = false;
    }

    mincost[0] = 0;
    int res = 0;

    while (true) {
        int v = -1;
        for (int u = 0; u < V; u++) {
            if (!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
        }

        if (v == -1) break;
        used[v] = true;
        res += mincost[v];

        for (int u = 0; u < V; u++) {
            if (cost[v][u] < mincost[u]) {
                mincost[u] = cost[v][u];
            }
        }
    }
    return res;
}

int main() {
    cin >> V;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cin >> cost[i][j];
            if (cost[i][j] == -1) cost[i][j] = INF;
        }
    }
    cout << prim() << endl;
    return 0;
}

C++: #include<iostream>
using namespace std;
static const int MAX =100;
static const int INFTY=(1<<21);
static const int WHITE=0;
static const int GRAY=1;
static 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]=INFTY;
    p[i]=-1;
    color[i]=WHITE;
  }
  d[0]=0;
  while(1){
    minv=INFTY;
    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];
	  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)?INFTY:e;
    }
  }
  cout<<prim()<<endl;
  return 0;
  
}