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 <bits/stdc++.h>
using namespace std;

#define ll long long int
#define P pair<ll,ll>

const ll INF = 10000000000;
struct edge{ll to,cost;};

int v;
vector<edge> g[100000];
ll d[100000];

int prim(){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(d,d+v,INF);
    int res = 0;
    d[0] = 0;
    que.push(P(0,0));

    while(!que.empty()){
        P p = que.top(); que.pop();
        ll k = p.second;
        if(d[k] < p.first){
            continue;
        }
        res += d[k];
        for(int i=0; i < g[k].size(); i++){
            edge e = g[k][i];
            if(d[e.to] > /*d[k]*/ + e.cost){
                d[e.to] = /*d[k] */+ e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
    return res;
}

int main() {

    int s;

    cin >> v;

    for(int i=0; i<v; i++){
        for(int j=0;j<v;j++){
            cin >> s;
            if(s!=-1){
                edge ed;
                ed.to = j;
                ed.cost = s;
                g[i].push_back(ed);
            }
        }
    }

    /*for(int i=0; i<v; i++){
        for(int j=0;j<g[i].size();j++){
            cout << g[i][j].to << "," << g[i][j].cost << " ";
        }
        cout << endl;
    }*/

    cout << prim() << endl;

    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <tuple>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <random>
#include <cstdlib>
#define INT_MAX 2147483647
#define INT_MIN -2147483646
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

static const int N = 105;

struct vertex {
	int id;
	int p;
	int d;
	bool operator<(const vertex & another) const {
		return (d != another.d ? d>another.d : id>another.id);
	}
};

int main() {
	vvi mx(N, vi(N, -1));
	int n;
	cin >> n;
	Loop(i, n) {
		Loop(j, n) {
			int a;
			cin >> a;
			mx[i][j] = a;
		}
	}
	//
	vi color(N, 0); //0,1
	priority_queue<vertex> q;
	q.push({ 0,-1,0});
	int ret = 0;
	while(q.size() > 0) {//?
		vertex v = q.top();
		q.pop();
		if (color[v.id] == 1) continue;
		color[v.id] = 1;
		ret += v.d;
		Loop(j, n) {
			if (mx[v.id][j] != -1 && color[j] != 1){
				q.push({ j, v.id,mx[v.id][j] });
			}
		}
	}
	cout << ret << endl;
	return 0;
}

C++: #if 0
time: 20min
using pair to store the edges' number, making it easier to find their nodes.					
#endif
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

int m,n,x,ans;
int P[100+10],edge1[10000+10],edge2[10000+10];


int root(int a){
	if (P[a] == a) return a;
	return (P[a] = root(P[a]));
}

bool same(int a, int b){
	return root(a)==root(b);
}
	
void unite(int a, int b){
	P[root(a)] = root(b);
}

int main() {
	pair<int,int> edges[10000+10];
	cin >> n;
	
	for (int i=1; i<=n; i++){
		P[i] = i;
	}
	
	m = 0;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			cin >> x;
			if (x>-1){
				edge1[m] = i;
				edge2[m] = j;
				edges[m] = make_pair(x, m);
				m+=1;
			}
		}
	}
	
	sort(edges, edges+m);
	n=1;
	for (int i=0; i<m; i++){
		if (n>=m) break;
		if (!same(edge1[edges[i].second], edge2[edges[i].second])){
			unite(edge1[edges[i].second], edge2[edges[i].second]);
			ans += edges[i].first;
			n+=1;
		}
	}
	
	cout << ans << endl;
	
}

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

int x[10000][10000];
int MIN[10000];
int MINX = 0;
int MINZ = 100;

int main() {
	memset(MIN, 127, sizeof(MIN));
	int n, a;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a;
			x[i][j] = a;
		}
	}
	for(int h=0;h<n;h++){
		memset(MIN, 127, sizeof(MIN));
		MINX=0;
		MIN[h] = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					if (x[j][k] != -1) {
						MIN[k] = min(MIN[k], x[j][k]);
					}
				}
			}
		}
		for (int i = 0; i < n; i++) {
			MINX += MIN[i];
		}
		MINZ=min(MINZ,MINX);
	}
	cout << MINZ << endl;
	return 0;
}

C++: #include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 1010;
const int INFTY = 1000000000;
struct Node{
    int to;
    int value;
    void set(int a,int b){
        to  = a;
        value = b;
    }
    void real(){
        value*=-1;
    }
};
bool operator<(const Node&a,const Node &b){
    return a.value<b.value;
}
vector<Node> g[maxn];
priority_queue<Node> q;
int d[maxn];
bool vis[maxn];
int p[maxn];
int n;
void prim(){
    for(int i = 0;i<n;++i){
        d[i] = INFTY;
        vis[i] = false;
        p[i] = -1;
    }
    d[0] = 0;
    Node work;
    work.set(0,0);
    q.push(work);
    while(!q.empty()){
        work = q.top();
        work.real();
        q.pop();
        int from = work.to;
        int len = g[from].size();
        if(vis[from])continue;
        vis[from] = true;
        while(len--){
            int to = g[from][len].to;
            int add = g[from][len].value;
            if(!vis[to]&&(add<d[to])){
                d[to] = add;
                p[to] = from;
                work.set(to,d[to]);
                work.real();
                q.push(work);
            }
        }
    }
}
int main(){
    int tmp,ans;
    Node work;
    scanf("%d",&n);
    for(int i = 0;i<n;++i){
        for(int j  = 0;j<n;++j){
            scanf("%d",&tmp);
            if(tmp!=-1){
                work.set(j,tmp);
                g[i].push_back(work);
            }
        }
    }
    prim();
    ans = 0;
    for(int i = 0;i<n;++i){
        ans+=d[i];
    }
    printf("%d\n",ans);
    return 0;
}