Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const BIG_COST = 3000

const (
	ST_NOT_YET = iota
	ST_JOINED
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	nNodes := scanInt(sc)
	costs := make([][]int, nNodes)

	for r := 0; r < nNodes; r++ {
		costs[r] = make([]int, nNodes)
		for c := 0; c < nNodes; c++ {
			costs[r][c] = scanInt(sc)
		}
	}

	states := make([]int, nNodes)
	minCosts := make([]int, nNodes)

	for i := 1; i < nNodes; i++ {
		minCosts[i] = BIG_COST
	}

	for {
		var u int
		minCost := BIG_COST

		for i := 0; i < nNodes; i++ {
			if states[i] != ST_JOINED && minCosts[i] < minCost {
				minCost = minCosts[i]
				u = i
			}
		}

		// 全てのノードが MST に JOIN できたので終了。
		if minCost == BIG_COST {
			break
		}

		states[u] = ST_JOINED

		for v := 0; v < nNodes; v++ {
			cost := costs[u][v]

			// MST内の u と MST外の v との辺の重みをそれぞれ minCosts[v] として
			// 保存しておく。このうち辺の重みが最小となる v が次のループで MST に JOIN する。
			if states[v] != ST_JOINED && cost != -1 && cost < minCosts[v] {
				minCosts[v] = cost
			}
		}
	}

	sum := 0
	for _, cost := range minCosts {
		sum += cost
	}
	fmt.Println(sum)
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

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;
}