Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	seen := make([]bool, n)
	for i := range list {
		list[i] = make([]int, n)
		for j := range list[i] {
			list[i][j] = scanInt()
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	sum := 0
	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if seen[node.id] {
			continue
		}
		seen[node.id] = true
		sum += node.weight

		for i, w := range list[node.id] {
			if w < 0 {
				continue
			}
			heap.Push(h, Node{id: i, weight: w})
		}
	}

	fmt.Println(sum)
}

C++: //---------------------------------------------------------------------------
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused

class TEdge;
struct TNode
{
	int TreeIndex;
	std::vector<const TEdge*> Connected;
	
	TNode();
	void SetIndex(int Index, const TEdge* Edge);
};

class TEdge
{
	std::pair<TNode*, TNode*> FEnds;
	int FWeight;
public:
	TEdge(TNode* EndA, TNode* EndB, int Weight);
	
	bool operator<(const TEdge& Other)const;
	int  Weight()const {return FWeight;}
	bool ToMekeCycle()const;
	
	void JoinTree(int TreeIndex)const;
};

TNode::TNode()
:TreeIndex(0)
{
}

void TNode::SetIndex(int Index, const TEdge* Edge)
{
	if(TreeIndex >= Index) return;
	TreeIndex = Index;
	for(std::vector<const TEdge*>::const_iterator It = Connected.begin(); It != Connected.end(); ++It){
		(*It)->JoinTree(Index);
	}
	Connected.push_back(Edge);
}

TEdge::TEdge(TNode* EndA, TNode* EndB, int Weight)
:FEnds(EndA, EndB), FWeight(Weight)
{
}

bool TEdge::operator<(const TEdge& Other)const
{
	return Weight() < Other.Weight();
}

bool TEdge::ToMekeCycle()const
{
	return FEnds.first->TreeIndex > 0 && FEnds.first->TreeIndex == FEnds.second->TreeIndex;
}

void TEdge::JoinTree(int TreeIndex)const
{
	FEnds.first->SetIndex(TreeIndex, this);
	FEnds.second->SetIndex(TreeIndex, this);
}

class TGraph
{
	std::vector<TNode> FNodes;
	std::vector<TEdge> FEdges;
public:
	TGraph(int NodeCount);
	
	void AddEdge(int NodeIndexA, int NodeIndexB, int Weight);
	int WeightMinimumSpanningTree();
};

TGraph::TGraph(int NodeCount)
:FNodes(NodeCount)
{
}

void TGraph::AddEdge(int NodeIndexA, int NodeIndexB, int Weight)
{
	if(NodeIndexA <= NodeIndexB || Weight < 0) return;
	FEdges.push_back(TEdge(&FNodes[NodeIndexA], &FNodes[NodeIndexB], Weight));
}

int TGraph::WeightMinimumSpanningTree()
{
	std::sort(FEdges.begin(), FEdges.end());
	unsigned int TreeCount = 0;
	int Weight = 0;
	for(std::vector<TEdge>::iterator It = FEdges.begin(); It != FEdges.end() && TreeCount < FNodes.size() - 1; ++It){
		if(It->ToMekeCycle()) continue;
		It->JoinTree(TreeCount + 1);
		Weight += It->Weight();
		++TreeCount;
	}
	return Weight;
}

int main()
{
	int NodeCount;
	std::cin >> NodeCount;
	TGraph Graph(NodeCount);
	
	for(int i = 0; i < NodeCount; ++i)
	{
		for(int j = 0; j < NodeCount; ++j){
			int Weight;
			std::cin >> Weight;
			Graph.AddEdge(i, j, Weight);
		}
	}
	
	std::cout << Graph.WeightMinimumSpanningTree() << std::endl;
	return 0;
}
//---------------------------------------------------------------------------

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;
}