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<iostream>
#include<cstdio>
#define W 0
#define G 1
#define B 2
#define inf 5000
#define MAX 100
#define NIL -1
using namespace std;

int n;
int A[MAX][MAX];

int Prim(){
    int color[MAX],d[MAX],p[MAX];
    int min,u,sum = 0;
    for(int i = 0; i < n; i++){
        color[i] = W;
        d[i] = inf;
        p[i] = NIL;
    }
    
    d[0] = 0;
    
    while(1){
        u = -1;
        min = inf;
        for(int i = 0; i < n; i++){
            if(d[i] < min && color[i] != B){
                u = i;
                min = d[i];
            }
        }
        
        if(u == -1) break;
            
        color[u] = B;
            
        for(int i = 0; i < n; i++){
            if(color[i] != B && A[u][i] != NIL){
                if(A[u][i] < d[i]){
                    d[i] = A[u][i];
                    color[i] = G;
                    p[i] = u;
                }
            }
        }
    }
    
    for(int i = 0; i < n; i++) {
        
        if(p[i] != -1) sum += A[i][p[i]];
        
    }
    
    return sum;
     
}

int main(){
    int x;
    scanf("%d",&n);
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j++){
            scanf("%d",&x);
            if( x == -1) A[i][j] = NIL;
            else A[i][j] = x; 
        }
    }
    
    cout << Prim() << endl;
    return 0;
}

C++: #if 0
????????£????????????1.5h
??¢?????????????????§??????????????¢??°????????£????????????sum????¨??????¨????????????????????£????????§?????????
???????????¢??????????????§????????????????????????????????????"-1"???????????????????????????????????§???????????§????????¨???????°???????????????????
#endif

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

int P[10000+10];

void init(int N){
	for(int i=0;i<=N;++i) P[i]=i;
}
int root(int a){
	if(P[a]==a)return a;
	else return(P[a]=root(P[a]));
}
bool is_same_set(int a,int b){
	return root(a)==root(b);
}
void unite(int a,int b){
	P[root(a)]=root(b);
}
int 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[j][i]; //???????????\???
		}
	}

	int M = 0; 
	int cost[N*N],src[N*N],dst[N*N];
	for (int r=0; r<N;r++)
		for (int c=0; c<r;c++) //r<c???????§?????????????
			if (A[r][c] > -1) {
				cost[M] = A[r][c];
				src[M] = r;
				dst[M] = c;
				M += 1;
			}
	pair<int,int> edges[2000+100];
	for(int i=0;i<M;i++)
		edges[i]=make_pair(cost[i],i); //first???????????????second???ID
	sort(edges,edges+M);
	
	//for(int i=0;i<M;++i)
		//cout<<edges[i].first<<endl;

	init(N);
	int sum=0;
	for(int i=0;i<M;i++){
		if(is_same_set(src[edges[i].second],dst[edges[i].second])==0){
			unite(src[edges[i].second],dst[edges[i].second]);
			sum+=edges[i].first;
		}
	}
		cout<<sum<<endl;
}

C++: #include <stdio.h>
#include <math.h>
#include <vector>
 
using namespace std;
 
int main(){
 
    int n,tmp,sum=0,tmp_min;
    scanf("%d",&n);
    int table[n][n],check[n],num_of_group=0,parent,child;
    vector<int> Group;
 
    for(int i=0;i<n;i++){
        for(int k=0;k<n;k++){
            scanf("%d",&tmp);
            table[i][k]=tmp;
        }
        check[i]=0;
    }
 
    Group.push_back(0);
    check[0]=1;
    num_of_group = 1;
    while(num_of_group<n){
        tmp_min=2001;
 
        for(int i=0;i<num_of_group;i++){
            for(int k=0;k<n;k++){
                if(table[Group[i]][k]!=-1&&check[k]==0&&table[Group[i]][k]<tmp_min){
                    tmp_min = table[Group[i]][k];
                    parent=Group[i];
                    child = k;
                }
            }
        }
        Group.push_back(child);
        sum+=table[parent][child];
        check[child]=1;
        num_of_group++;
    }
 
    printf("%d\n",sum);
 
    return 0;
}

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

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

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;
		}
	}
	MIN[0] = 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], MIN[j] + x[j][k]);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		MINX = max(MINX, MIN[i]);
	}
	cout << MINX << endl;
	return 0;
}