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 <stdio.h>
#include <iostream>
#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#define N 10000
using namespace std;

class edge
{
  public:
    int i, j, weigt;
    bool operator()(edge e1, edge e2)
    {
        return e1.weigt < e2.weigt;
    }
};
edge e[N];
vector<int> adj[N];
int n;
int c = 0;
int f[N] = {};
int g[N] = {};

void setGraphNum(int v, int i)
{
    g[v] = i;
    f[v]++;
    vector<int>::iterator itr = adj[v].begin();
    while (itr != adj[v].end())
    {
        if (f[*itr] != c)
            setGraphNum(*itr, i);
        itr++;
    }
}
void CalcGraphNum()
{
    int k = 1;
    for (int i = 0; i < n; i++)
    {
        if (f[i] != c)
            setGraphNum(i, k++);
    }
}
int main()
{
    cin >> n;
    int k = 0, tmp = 0, sum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> tmp;
            if (j < i + 1 || tmp < 0)
                continue;
            e[k].i = i;
            e[k].j = j;
            e[k].weigt = tmp;
            k++;
        }
    }
    sort(e, e + k, edge());
    for (int i = 0; i < n; i++)
        g[i] = i;
    for (int i = 0; i < k; i++)
    {
        if (g[e[i].i] == g[e[i].j])
            continue;
        adj[e[i].i].push_back(e[i].j);
        adj[e[i].j].push_back(e[i].i);
        sum += e[i].weigt;
        //cout << e[i].i << " " << e[i].j << " " << e[i].weigt << "\n";
        if (++c == n - 1)
            break;
        CalcGraphNum();
    }

    cout << sum << "\n";
    return 0;
}

C++: #include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

int prim() {
  int u, minv;
  int d[MAX], p[MAX], color[MAX];

  for ( int i = 0; i < n; i++ ) {
    d[i] = INFTY;
    p[i] = -1;
    color[i] = WHITE;
  }

  d[0] = 0;

  while ( 1 ) {
    minv = INFTY;
    u = -1;
    for ( int i = 0; i < n; i++ ) {
      if ( minv > d[i] && color[i] != BLACK ) {
        u = i;
        minv = d[i];
      }
    }
    if ( u == -1 ) break;
    color[u] = BLACK;
    for ( int v = 0; v < n; v++ ) {
      if ( color[v] != BLACK && M[u][v] != INFTY ) {
        if( d[v] > M[u][v] ) {
          d[v] = M[u][v];
          p[v] = u;
          color[v] = GRAY;
        }
      }
    }
  }
  int sum = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( p[i] != -1 ) sum += M[i][p[i]];
  }

  return sum;
}

int main() {
  cin >> n;

  for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++ ) {
      int e; cin >> e;
      M[i][j] = (e == -1) ? INFTY : e;
    }
  }

  cout << prim() << endl;

  return 0;
}

C++: #include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

int prim(){
    int u, minv;
    int d[MAX], p[MAX], color[MAX];
    
    for(int i = 0; i < n; i++){
        d[i] = INFTY;
        p[i] = -1;
        color[i] = WHITE;
    }
    
    d[0] = 0;
    
    while(1){
        minv = INFTY;
        u = -1;
        for(int i = 0; i < n; i++){
            if((minv > d[i]) && (color[i] != BLACK)){
                u = i;
                minv = d[i];
            }
        }
        if(u == -1) break;
        color[u] = BLACK;
        for(int v = 0; v < n; v++){
            if((color[v] != BLACK) && (M[u][v] != INFTY)){
                if(d[v] > M[u][v]){
                    d[v] = M[u][v];
                    p[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    int sum = 0;
    for(int i = 0; i < n; i++){
        if(p[i] != -1) sum += M[i][p[i]];
    }
    
    return sum;
}

int main(){
    cin >> n;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int e;
            cin >> e;
            M[i][j] = (e == -1) ? INFTY : e;
        }
    }
    
    cout << prim() << endl;
    
    return 0;
}

C++: #include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

/*int find(int x) 
{
	if (x == parent[x])return x;
	else 
	{
		return parent[x] = find(parent[x]);
	}
}

bool isSame(int x, int y)
{
	return find(x) == find(y);
}

void unite(int x, int y) 
{
	x = find(x);
	y = find(y);

	if (x == y)return;

	if (Rank[x] < Rank[y]) 
	{
		parent[x] = y;
	}
	else
	{
		parent[y] = x;
		if (Rank[x] == Rank[y])Rank[x]++;
	}
}*/

struct UnionFind
{
	vector<int> parent;
	vector<int> rank;

	UnionFind(int n) :parent(n), rank(n, 0)
	{
		for (int i = 0; i < n; i++)
		{
			parent[i] = i;
		}
	}

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

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (x == y)
		{
			return;
		}

		if (rank[x] < rank[y])
		{
			parent[x] = y;
		}
		else
		{
			parent[y] = x;
			if (rank[x] == rank[y])
			{
				rank[x]++;
			}
		}
	}

	bool same(int x, int y)
	{
		return find(x) == find(y);
	}
};

struct Edge
{
	int v1, v2, cost;
	Edge(int v1, int v2, int cost) :v1(v1), v2(v2), cost(cost){}
	bool operator<(const Edge& e)const
	{
		return cost < e.cost;
	}
};

int main()
{
	int n;
	cin >> n;

	vector<Edge> e;
	UnionFind uf(n);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int c;
			cin >> c;
			if (c != -1)
			{
				e.push_back(Edge(i, j, c));
			}
		}
	}

	sort(e.begin(), e.end());

	int cost = 0;
	for(auto& te:e)
	{
		if (!uf.same(te.v1, te.v2))
		{
			uf.unite(te.v1, te.v2);
			cost += te.cost;
		}
	}

	cout << cost << endl;

	return 0;
}