Go: package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	I int
	J int
	A int
}

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]int, n)
	edges := make([]Edge, 0, n*(n-1)/2)
	parents := make([]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&g[i][j])
			if g[i][j] >= 0 {
				edges = append(edges, Edge{i, j, g[i][j]})
			}
		}
		parents[i] = i
	}
	sort.SliceStable(edges, func(i, j int) bool { return edges[i].A >= edges[j].A })

	sum := 0
	num := 0
	for len(edges) > 0 && num < n-1 {
		edge := edges[len(edges)-1]
		edges = edges[:len(edges)-1]

		if same(edge.I, edge.J, &parents) {
			continue
		}
		union(edge.I, edge.J, &parents)
		sum += edge.A
		num += 1
	}
	fmt.Println(sum)
}



func root(id int, parents *[]int) int {
	if id == (*parents)[id] {
		return id
	}
	return root((*parents)[id], parents)
}

func union(i, j int, parents *[]int) {
	(*parents)[root(j, parents)] = (*parents)[root(i, parents)]
}

func same(i, j int, parents *[]int) bool {
	return root(i, parents) == root(j, parents)
}

C++: // ALDS1_12_A: Minimum Spanning Sort
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
bool debug = false;
const int INF = 100000;
// const int BK = 0, GR = 1, WT = 2;

std::vector<std::vector<int>> adjacency_list;
std::vector<int> node_stats;
std::vector<std::pair<int, int>> weight_memo;

int PrimAlgorithm(int weight, int vertex) {
    node_stats.at(vertex) = 1;
    
    for (int i=0; i<adjacency_list.at(vertex).size(); i++) {
        int tmp_vertex = i;
        if (adjacency_list.at(vertex).at(tmp_vertex) != -1) {
            std::pair<int,int> tmp = std::make_pair(tmp_vertex, adjacency_list.at(vertex).at(tmp_vertex));
            weight_memo.push_back(tmp);
        }
    }
    
    int minimum_weight = INF, next_vertex = -1;
    for (int i=0; i<weight_memo.size(); i++) {
        int tmp_vertex = weight_memo.at(i).first, tmp_weight = weight_memo.at(i).second + weight;
        if (tmp_weight < minimum_weight) {    
            if (node_stats.at(tmp_vertex) == 0) {
                next_vertex = tmp_vertex;
                minimum_weight = tmp_weight;
            }
        }
    }
    if (debug) std::cout << "next_vertex = " << next_vertex << ", minimum_weight = " << minimum_weight << "\n";
    if (next_vertex == -1) {
        return weight;
    }
    return PrimAlgorithm(minimum_weight, next_vertex);
}

int main() {
    int total_num; std::cin >> total_num;
    adjacency_list.resize(total_num);
    for (int i=0; i<adjacency_list.size(); i++) adjacency_list.at(i).resize(total_num);
    for (int i=0; i<total_num; i++) {
        for(int j=0; j<total_num; j++) {
            std::cin >> adjacency_list.at(i).at(j);
        }
    }

    node_stats.resize(total_num);
    for (int i=0; i<node_stats.size(); i++) node_stats.at(i) = 0;

    int result = PrimAlgorithm(0, 0);
    std::cout << result << "\n";
}

C++: #define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream &operator << (ostream &os, const vector<T> &);
template<size_t n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, const tuple<T...> &){}
template<size_t n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream &os, const tuple<T...> &t){
    os << (n == 0 ? "" : " ") << get<n>(t); _ot<n+1>(os, t);
}
template<class...T> ostream &operator << (ostream &os, const tuple<T...> &t){
    _ot<0>(os, t); return os;
}
template<class T, class U> ostream & operator << (ostream &os, const pair<T,U> &p){
    return os << "(" << p.first << ", " << p.second << ") ";
}
template<class T> ostream &operator << (ostream &os, const vector<T> &v){
    for(size_t i = 0; i < v.size(); i++) os << v[i] << (i + 1 == v.size() ? "" : ", "); return os;
}
#ifdef DEBUG
#define dump(...) (cerr << #__VA_ARGS__ << " = " << make_tuple(__VA_ARGS__) \
                   << " (L : " << __LINE__ << ")" << endl)
#else
#define dump(...)
#endif
#define all(c) begin(c), end(c)
#define range(i,a,b) for(int i = a; i < (int)(b); i++)
#define rep(i,b) range(i,0,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
void fastios(){ ios_base::sync_with_stdio(0); cin.tie(0); }
int const mod = 1000000007;
auto const inf = numeric_limits<int>::max()/8;

using Weight = int;
using Capacity = int;
struct Edge {
    int src, dst; Weight weight;
    Edge(int s, int d, int w) : src(s), dst(d), weight(w) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

struct UnionFind {
    vector<int> par;
    int cnt;
    UnionFind(int size_) : par(size_, -1), cnt(size_) { }
    bool merge(int x, int y){
        x = find(x); y = find(y);
        if (x != y) {
            if (par[y] < par[x]) swap(x, y);
            par[x] += par[y]; par[y] = x; cnt--;
        }
        return x != y;
    }
    bool get(int x, int y){ return find(x) == find(y); }
    int find(int x){ return par[x] < 0 ? x : par[x] = find(par[x]); }
    int size(int x){ return -par[find(x)]; }
    int size(){ return cnt; }
};

bool operator < (const Edge &e, const Edge &f){ return e.weight > f.weight; }
pair<Weight, Edges> kruskal(Graph const& g){
    UnionFind uf(g.size());
    Edges es; rep(i, g.size()) for(auto &e : g[i]) es.emplace_back(e);
    sort(all(es)); reverse(all(es)); // !! INVERSE !!
    Weight total = 0; Edges T;
    for(auto &e : es){
        if(uf.get(e.src,e.dst)) continue;
        T.push_back(e); total += e.weight; uf.merge(e.src,e.dst);
    }
    return make_pair(total, T);
}

int main(){
    int n;
    cin >> n;
    Graph g(n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int x;
            cin >> x;
            if(x != -1) g[i].emplace_back(i,j,x);
        }
    }
    cout << kruskal(g).first << endl;
}