Go: package main

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

const (
	MAX_N      = 200
	MAX_WEIGHT = 2000
)

type Edge struct {
	start  int
	end    int
	weight int
}

type ShortestInfo struct {
	edges    []Edge
	shortest int
}

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

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	shortestList := make([]ShortestInfo, n)
	for i := 1; i < n; i++ {
		shortestList[i] = ShortestInfo{edges: []Edge{}, shortest: MAX_N*MAX_WEIGHT + 1}
	}

	adjacentMatrix := make([][]int, n)
	for i := 0; i < n; i++ {
		adjacentMatrix[i] = make([]int, n)
		for j := 0; j < n; j++ {
			v, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			adjacentMatrix[i][j] = v
		}
	}

	mst([]int{1}, shortestList, adjacentMatrix)
	fmt.Println(calculateMinWeight(shortestList))
}

func calculateMinWeight(shortestList []ShortestInfo) int {
	visitedList := make([]bool, len(shortestList))
	visitedList[0] = true
	sumWeight := 0
	for !visitedAll(visitedList) {
		shortestInfo := shortestList[0]
		shortestList = shortestList[1:]
		edges := shortestInfo.edges
		for _, edge := range edges {
			if !visitedList[edge.end-1] {
				visitedList[edge.end-1] = true
				sumWeight += edge.weight
			}
		}
	}
	return sumWeight
}

func visitedAll(visitedList []bool) bool {
	for _, v := range visitedList {
		if !v {
			return false
		}
	}
	return true
}

func mst(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]int) {
	for len(nodeStack) > 0 {
		currentNode := nodeStack[0]
		nodeStack = nodeStack[1:]
		currentShortest := getShortest(currentNode, shortestList)
		adjacents := findAdjacents(currentNode, adjacentMatrix)
		for i := 0; i < len(adjacents); i++ {
			adj := adjacents[i]
			s := getShortest(adj.end, shortestList)
			if currentShortest.shortest+adj.weight < s.shortest || (currentShortest.shortest+adj.weight == s.shortest && len(currentShortest.edges)+1 > len(s.edges)) {
				setShortest(adj.end, adj, currentShortest, shortestList)
				nodeStack = append(nodeStack, adj.end)
			}
		}
	}
}

func getShortest(node int, shortestList []ShortestInfo) ShortestInfo {
	return shortestList[node-1]
}

func setShortest(node int, edge Edge, currentShortest ShortestInfo, shortestList []ShortestInfo) {
	newEdges := make([]Edge, len(currentShortest.edges)+1)
	for i := 0; i < len(newEdges)-1; i++ {
		newEdges[i] = currentShortest.edges[i]
	}
	newEdges[len(newEdges)-1] = edge
	shortestInfo := ShortestInfo{edges: newEdges, shortest: currentShortest.shortest + edge.weight}
	shortestList[node-1] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]int) []Edge {
	adjacents := adjacentMatrix[currentNode-1]
	edges := []Edge{}
	for i, v := range adjacents {
		if v > 0 {
			edges = append(edges, Edge{start: currentNode, end: i + 1, weight: v})
		}
	}
	return edges
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

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

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

using namespace std;

#define INF 2001
#define NIL -2


struct node{
    int key=INF, pi=NIL, flag=0;
};

node grf[101];
int hv[101][101], n;

void search(){
    int min = INF, mini = NIL;
    for(int i=0;i<n;++i){
        if(grf[i].flag != 1 && grf[i].key < min){
            min = grf[i].key;
            mini= i;
        }
    }
    
    if(min == INF){
        return;
    }
    
    grf[mini].flag = 1;
    for(int j=0;j<n;++j){
        if((grf[j].flag != 1 && hv[mini][j] != -1) && hv[mini][j] < grf[j].key){
            grf[j].key = hv[mini][j];
            grf[j].pi = mini;
        }
    }
    
    return;
    
}

int main(){
    int total=0;
    cin >> n;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cin >> hv[i][j];
        }
    }
    
    grf[0].key = 0;
    grf[0].flag = 1;
    for(int j=0;j<n;++j){
        if(hv[0][j] != -1 && hv[0][j] < grf[j].key){
            grf[j].key = hv[0][j];
            grf[j].pi = 0;
        }
    }
    
    for(int i=1;i<n;++i){
        search();
    }
    
    for(int i=0;i<n;++i){
        total+=grf[i].key;
    }
    
    cout << total << endl;
    
    return 0;
}