Go: package main

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

// Define disjoint-set forests

type vertexNo int

type vertex struct {
	number vertexNo
	rank int
	parent *vertex
}

func makeSet(number vertexNo) vertex {
	return vertex {
		number: number,
		rank: 0,
		parent: nil,
	}
}

func union(x, y *vertex) *vertex {
	return link(findSet(x), findSet(y))
}

func link(x, y *vertex) *vertex {
	if x.rank > y.rank {
		y.parent = x
		return x
	} else {
		x.parent = y
		if x.rank == y.rank {
			y.rank += 1
		}
		return y
	}
}

func findSet(v *vertex) *vertex {
	if v.parent == nil {
		return v
	}
	v.parent = findSet(v.parent)
	return v.parent
}

// Function to calculate minimum spanning tree

type matrix [][]int

type edge struct {
	one vertexNo
	two vertexNo
	weight int
}

const(
	MAX_VERTICES = 100
)

func newEdgesFromMatrix(matrix matrix) []edge {
	edges := make([]edge, 0, MAX_VERTICES * MAX_VERTICES)

	for i := 0; i < len(matrix); i++ {
		row := matrix[i]
		for j := i; j < len(row); j++ {
			if row[j] >= 0 {
				edge := edge{one: vertexNo(i+1), two: vertexNo(j+1), weight: row[j]}
				edges = append(edges, edge)
			}
		}
	}

	return edges
}

func solve(matrix matrix) int {
	nVertices := len(matrix)

	// initialize vertices
	vertices := make([]vertex, nVertices)
	for i := 0; i < nVertices; i++ {
		vertices[i] = makeSet(vertexNo(i+1))
	}

	// prepare edges sorted in the ascending order of weight
	edges := newEdgesFromMatrix(matrix)
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})

	unionCount := 0
	weightSum := 0
	for unionCount < nVertices-1 {
		for i := 0; i < len(edges); i++ {
			edge := edges[i]
			v1 := &vertices[edge.one-1]
			v2 := &vertices[edge.two-1]
			rep1 := findSet(v1)
			rep2 := findSet(v2)
			if rep1.number == rep2.number {
				continue
			}
			union(rep1, rep2)
			edges = append(edges[0:i], edges[i+1:]...)
			weightSum += edge.weight
			unionCount++
			break
		}
	}

	return weightSum
}

// main

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

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

	matrix := parseMatrix(n, sc)

	edges := newEdgesFromMatrix(matrix)
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})

	fmt.Println(solve(matrix))
}

func parseMatrix(n int, sc *bufio.Scanner) [][]int {
	matrix := make([][]int, n)
	for i := 0; i < n; i++ {
		matrix[i] = make([]int, n)
		for j := 0; j < n; j++ {
			x, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			matrix[i][j] = x
		}
	}
	return matrix
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

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

C++: #include "stdafx.h"
#include <iostream>

#define MAX 100000000;
using namespace std;

int main(void)
{
	int n, now = 0, flag[101] = {};
	long ans = 0, an[100][100], min[100];

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> an[i][j];
		min[i] = MAX;
	}

	do {
		long key = , key_i;
		flag[now] = 1;
		flag[100] = 0;

		for (int i = 0; i < n; i++) {
			if (an[now][i] != -1 && an[now][i] < min[i] && flag[i] == 0)
				min[i] = an[now][i];
			if (flag[i] == 0 && min[i] < key) {
				key = min[i];
				key_i = i;
			}
			if (flag[i] == 1)
				flag[100]++;
		}

		now = key_i;
		ans += key;

	} while (flag[100] != n - 1);

	cout << ans << endl;

	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << '\n'
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
constexpr int MAX = 101;
constexpr int INF = 1<<21;
enum Color { WHITE = 0, GRAY, BLACK };
int n;
vv(int, M, MAX, MAX, INF);
inline int prim() {
    vi d(n, INF), t(n, -1), color(n, WHITE);
    d[0] = 0;
    int minv, u;
    while(true) {
        minv = INF;
        u = -1;
        rep(i, 0, n) {
            if(minv > d[i] && color[i] != BLACK) {
                u = i;
                minv = d[i];
            }
        }
        if(u == -1) break;
        color[u] = BLACK;
        rep(v, 0, n) {
            if(color[v] != BLACK && d[v] > M[u][v]) {
                d[v] = M[u][v];
                t[v] = u;
                color[v] = GRAY;
            }
        }
    }
    return accumulate(all(d), 0);
}
int main() {
    cin >> n;
    int e;
    rep(i, 0, n) {
        rep(j, 0, n) {
            cin >> e;
            if(e != -1) M[i][j] = e;
        }
    }
    P(prim());
    return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <bitset>
#include <numeric>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <tuple>

using namespace std;

#define int long long

#define rep(i,n) for(int i = 0; i<n ; i++)
#define FOR(i,a,n) for(int i=a; i<n; i++)
#define REPSTR(i,s) for(int i=0; (s)[i]; i++)
#define REPITR(i,s) for(auto i=(s).begin(); i!=(s).end();i++)

#define RANGE(a,i,b) ((a)<=(i)&&(i)<=(b))

#define pb push_back
#define mp make_pair

#define ALL(a) begin(a), end(a)

#define EXIST(s,x) ((s).find(x)!=(s).end())

#define SET(a,c) memset(a,c,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))

#ifdef _DEBUG
#define DEBUG(x) cerr<<#x<<":"<<x<<endl
#else
#define DEBUG(x)
#endif

#define PRINTJOIN(x,n) rep(i,n){if(i)cout<<" ";cout<<x[i];}cout<<endl 

#define INF 1001001001
#define LLINF 1001001001001001001LL

typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef stringstream SS;

#define PQ priority_queue

#define FST first
#define SEC second

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

template<typename T>
class UnionFind {
    public:
    vector<T> parent;
    vector<T> rank;
    UnionFind() {}
    UnionFind(T n):parent(n), rank(n){
        rep(i, n) {
            parent[i]=i;
        }
        fill(ALL(rank), 0);
    }
    T root(T x) {
        if(parent[x] == x){
            return x;
        } else {
            parent[x] = root(parent[x]);
            return parent[x];
        }
    }
    bool same(T x, T y) {
        return root(x) == root(y);
    }
    void unite(T x, T y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else {
            parent[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }
};

signed main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n;
    cin>>n;
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> q;
    rep(i,n)rep(j,n){
        int t;cin>>t;
        if(t != -1) {
            q.push(make_tuple(t, i, j));
        }
    }
    UnionFind<int> uf(n);
    int ans = 0;
    while(!q.empty()) {
        tuple<int,int,int> t = q.top();q.pop();
        int c,x,y;
        c=get<0>(t);
        x=get<1>(t);
        y=get<2>(t);
        if(!uf.same(x,y)) {
            ans += c;
            uf.unite(x,y);
        }
    }
    cout<<ans<<endl;
	return 0;
}