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 <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
const long long INFLL = 1LL << 60;
const int INFINT = 1 << 30;
const long long MOD = 1e9 + 7;

vector<vector<int>> G(101, vector<int>(0));
vector<int> c(101, 0);
vector<int> d(101, 0);
vector<int> f(101, 0);

template <class T> using vec_alias = ::std::vector<T>;

template <class T> void vecout(T V) {
    auto t = V.begin();
    while(t != V.end()) {
        cout << " " << *t++;
        // if(t != V.end()) cout << " ";
    }
    cout << endl;
};

int t = 0;
void dfs(int i) {
    if(c[i]) return;
    c[i] = 1;
    d[i] = ++t;
    for(auto e : G[i])
        dfs(e);
    f[i] = ++t;
}

class node {
  public:
    int dist = -1;
    vector<int> nex;
};

template <template <class> class Container> class union_find {
  protected:
    class node_type;

  public:
    using container_type = Container<node_type>;
    using size_type = typename container_type::size_type;

  protected:
    class node_type {
      public:
        typename union_find::size_type parent;
        typename union_find::size_type size;
    };

    container_type tree;

  public:
    union_find() : tree() {}
    explicit union_find(const size_type size) : tree(size, {0, 1}) {
        for(size_type i = 0; i < size; ++i)
            tree[i].parent = i;
    }

    bool empty() const { return tree.empty(); }
    size_type size() const { return tree.size(); }

    size_type find(size_type x) {
        assert(x < size());
        while(tree[x].parent != x)
            x = tree[x].parent = tree[tree[x].parent].parent;
        return x;
    }
    bool same(const size_type x, const size_type y) {
        assert(x < size());
        assert(y < size());
        return find(x) == find(y);
    }
    size_type size(const size_type x) {
        assert(x < size());
        return tree[find(x)].size;
    }

    ::std::pair<size_type, size_type> unite(size_type x, size_type y) {
        assert(x < size());
        assert(y < size());
        x = find(x);
        y = find(y);
        if(x != y) {
            if(tree[x].size < tree[y].size) ::std::swap(x, y);
            tree[x].size += tree[y].size;
            tree[y].parent = x;
        }
        return {x, y};
    }
};

class edge {
  public:
    int f;
    int t;
    int c;

    edge() {
        f = -1;
        t = -1;
        c = -1;
    }
    edge(int _f, int _t, int _c) {
        f = _f;
        t = _t;
        c = _c;
    }
};

bool operator<(const edge &a, const edge &b) { return a.c < b.c; };
bool operator>(const edge &a, const edge &b) { return a.c > b.c; };

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, c, t = 0;
    cin >> n;
    union_find<vec_alias> uf(n);
    priority_queue<edge, vector<edge>, greater<edge>> E;

    rep(i, n) rep(j, n) {
        cin >> c;
        if(c > -1) {
            edge tmp(i, j, c);
            E.push(tmp);
        }
    }

    while(!E.empty()) {
        edge e = E.top();
        E.pop();
        if(!uf.same(e.f, e.t)) {
            t += e.c;
            uf.unite(e.f, e.t);
        }
    }
    cout << t << endl;
}