Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	g := make([][]int, n)
	ans := make([][]int, n)

	inf := 1 << 30
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		ans[i] = make([]int, n)
		for ii := 0; ii < n; ii++ {
			g[i][ii] = getNextInt(scanner)
			if g[i][ii] == -1 {
				g[i][ii] = inf
			}
			ans[i][ii] = -1
		}
	}

	im := make(IntMap, 1)

	im.increment(1)

	for len(im) < n {
		min := inf
		u := -1
		v := -1
		for i := range im {
			for ii := 0; ii < n; ii++ {
				if im.get(ii) != 0 {
					continue
				}
				if min > g[i][ii] {
					min = g[i][ii]
					u = i
					v = ii
				}
			}
		}
		im.increment(v)
		ans[u][v] = min
		ans[v][u] = min
	}

	sum := 0
	for i := 0; i < n-1; i++ {
		for ii := i + 1; ii < n; ii++ {
			if ans[i][ii] != -1 {
				sum += ans[i][ii]
			}
		}
	}

	fmt.Fprintln(writer, sum)
	writer.Flush()
}

// IntMap ...
type IntMap map[int]int

func (m IntMap) get(key int) int {
	if _, ok := m[key]; ok {
		return m[key]
	}
	return 0
}
func (m IntMap) increment(key int) {
	if _, ok := m[key]; ok == false {
		m[key] = 0
	}
	m[key]++
}

C++: #include <cstdio>
using namespace std;
#define MAX_N (105)
#define INF (10000)
int n;
int G[MAX_N][MAX_N];
bool MST[MAX_N];
int DIST[MAX_N];		// MST??¨????????¢
int NEIGH[MAX_N];		// ??£??????

int main()
{
    scanf("%d", &n);
    for ( int i = 0; i < n; i++ ) {
	for ( int j = 0; j < n; j++ ) {
	    int d;
	    scanf("%d", &d);
	    G[i][j] = ( d == -1 ) ? INF : d;
	}
    }

    int r = 0;
    int size_mst = 1;

    MST[r] = true;
    
    for ( int i = 0; i < n; i++ ) {
	if ( i == r ) continue;
	DIST[i] = G[r][i];
	NEIGH[i] = r;
    }

    int ans = 0;

    while ( size_mst < n ) {
	int u = 0;
	int min_dist = INF;
	// ????°????????????¢???
	for ( int i = 0; i < n; i++ ) {
	    if ( !MST[i] ) {
		if ( DIST[i] < min_dist ) {
		    u = i;
		    min_dist = DIST[i];
		}
	    }
	}

	ans += min_dist;
	
	MST[u] = true;
	size_mst++;

	// MST??¨????????¢?????´??°
	for ( int i = 0; i < n; i++ ) {
	    if ( !MST[i] ) {
		if ( G[u][i] < DIST[i] ) {
		    DIST[i] = G[u][i];
		    NEIGH[i] = u;
		}
	    }
	}
    }

    printf("%d\n", ans);

    return 0;
}

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

using namespace std;

const int maxn=1e2+5;
const int inf=(1<<21);
const int white=0;
const int gray=1;
const int black=2;

int n,m[maxn][maxn];

int prim()
{
    int d[maxn],p[maxn],book[maxn];
    for(int i=0;i<n;i++){
        d[i]=inf;
        p[i]=-1;
        book[i]=0;
    }
    d[0]=0;
    int u,minv,sum=0;
    while(1){
        minv=inf;
        u=-1;
        for(int i=0;i<n;i++){
            if(minv>d[i]&&book[i]==0){
                u=i;
                minv=d[i];
            }
        }
        if(u==-1){
            break;
        }else{
            sum+=d[u];
        }
        book[u]=1;
        for(int v=0;v<n;v++){
            if(book[v]==0&&d[v]>m[u][v]){
                d[v]=m[u][v];
                p[v]=u;
            }
        }
    }
//    int sum=0;
//    for(int i=0;i<n;i++){
//        if(p[i]!=-1){
//            sum+=m[i][p[i]];
//        }
//    }
    return sum;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int e;
            cin>>e;
            m[i][j]=(e==-1)?inf:e;
        }
    }
    cout<<prim()<<endl;
    return 0;
}
/*
5
-1 2 3 1 -1
2 -1 -1 4 -1
3 -1 -1 1 1
1 4 1 -1 3
-1 -1 1 3 -1
*/

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;
typedef pair<int, int> P;   //cost, to
static const int INF = 1e9;
static const int SIZE = 101;
int par[SIZE];
int rk[SIZE];
int d[SIZE];
int n;

struct edge
{
	int u, v, cost;
};

struct edge2
{
	int to, cost;
};

bool comp(const edge& e1, const edge& e2)
{
	return(e1.cost < e2.cost);
}

void init()
{
	for (int i = 0; i < SIZE; ++i)
	{
		par[i] = i;
		rk[i] = 0;
	}
}

int find(int x)
{
	if (x == par[x])
	{
		return(x);
	}
	else
	{
		return(par[x] = find(par[x]));
	}
}

void unite(int a, int b)
{
	int x = find(a);
	int y = find(b);
	if (x == y)
	{
		return;
	}
	if (rk[x] < rk[y])
	{
		par[x] = y;
	}
	else
	{
		par[y] = x;
		if (rk[x] == rk[y])
		{
			++rk[x];
		}
	}
}

bool same(int a, int b)
{
	return(find(a) == find(b));
}

int kruskal(vector<edge>& es)
{
	init();
	int res = 0;
	sort(es.begin(), es.end(), comp);
	for (int i = 0; i < es.size(); ++i)
	{
		edge e = es[i];
		if (!same(e.u, e.v))
		{
			unite(e.u, e.v);
			res += e.cost;
		}
	}
	return(res);
}

int prim(vector<edge2>* G)
{
	vector<bool> isUsed(n);
	for (int i = 0; i < n; ++i)
	{
		isUsed[i] = false;
	}
	priority_queue<P, vector<P>, greater<P> > pque;
	P p = make_pair(0, 0);
	pque.push(p);
	int res = 0;
	while (!pque.empty())
	{
		P p = pque.top();
		pque.pop();
		int v = p.second;
		if (isUsed[v])
		{
			continue;
		}
		isUsed[v] = true;
		res += p.first;
		for (int i = 0; i < G[v].size(); ++i)
		{
			edge2 e = G[v][i];
			pque.push(P(e.cost, e.to));
		}
	}
	return(res);
}


void solve()
{
	cin >> n;

// For Kruskal
	//vector<edge> es;
	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		int cost;
	//		cin >> cost;
	//		if (cost != -1)
	//		{
	//			edge e;
	//			e.u = i;
	//			e.v = j;
	//			e.cost = cost;
	//			es.push_back(e);
	//		}
	//	}
	//}
	//cout << kruskal(es) << endl;

// For Prim
	vector<edge2> G[SIZE];
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			int cost;
			cin >> cost;
			if (j >= i && cost != -1)
			{
				edge2 e1, e2;
				e1.to = j;
				e1.cost = cost;
				e2.to = i;
				e2.cost = cost;
				G[i].push_back(e1);
				G[j].push_back(e2);
			}
		}
	}
	cout << prim(G) << endl;
}

int main()
{
	solve();
	return(0);
}

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

int main()
{
    int n,tmp,sum=0,MIN;
    int d[105],v[105],m[105][105],p,child;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cin>>tmp,m[i][j]=tmp;
        v[i]=0;
    }
    vector<int>G;
    v[0]=1;
    G.push_back(0);
    for(int M=1;M<n;M++)
    {
        MIN=2005;
        for(int i=0;i<M;i++)
            for(int j=0;j<n;j++)
                if(m[G[i]][j]!=-1&&!v[j]&&m[G[i]][j]<MIN)
                {
                    MIN=m[G[i]][j];
                    p=G[i];
                    child=j;
                }
        G.push_back(child);
        sum+=m[p][child];
        v[child]=1;
    }
    cout<<sum<<endl;
    return 0;
}