Go: package main

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

const BIG_COST = 3000

const (
	ST_NOT_YET = iota
	ST_JOINED
)

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

	nNodes := scanInt(sc)
	costs := make([][]int, nNodes)

	for r := 0; r < nNodes; r++ {
		costs[r] = make([]int, nNodes)
		for c := 0; c < nNodes; c++ {
			costs[r][c] = scanInt(sc)
		}
	}

	states := make([]int, nNodes)
	minCosts := make([]int, nNodes)

	for i := 1; i < nNodes; i++ {
		minCosts[i] = BIG_COST
	}

	for {
		var u int
		minCost := BIG_COST

		for i := 0; i < nNodes; i++ {
			if states[i] != ST_JOINED && minCosts[i] < minCost {
				minCost = minCosts[i]
				u = i
			}
		}

		// 全てのノードが MST に JOIN できたので終了。
		if minCost == BIG_COST {
			break
		}

		states[u] = ST_JOINED

		for v := 0; v < nNodes; v++ {
			cost := costs[u][v]

			// MST内の u と MST外の v との辺の重みをそれぞれ minCosts[v] として
			// 保存しておく。このうち辺の重みが最小となる v が次のループで MST に JOIN する。
			if states[v] != ST_JOINED && cost != -1 && cost < minCosts[v] {
				minCosts[v] = cost
			}
		}
	}

	sum := 0
	for _, cost := range minCosts {
		sum += cost
	}
	fmt.Println(sum)
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

C++: #include <iostream>
#include<algorithm>
using namespace std;


struct edge
{
   int cost;
   int src;
   int dst;
};

edge e[5000];
int A[100][100];
int M=0;
int P[100];

void init(int N)
{
  for (int i=0; i<=N; ++i) P[i] = i;
}

int root(int a)
{
  if (P[a] == a) return a;
  return (P[a] = root(P[a]));
}

bool is_same_set(int a, int b)
{
  return root(a) == root(b);
}

void unite(int a, int b)
{
  P[root(a)] = root(b);
}

void checkEdges(int n)
{
    for(int r=0;r<n;r++)
    {
        for(int c=r+1;c<n;c++)
            {
                if(A[r][c]>-1)
                    {
                        e[M].cost=A[r][c];
                        e[M].src=r;
                        e[M].dst=c;
                        M+=1;
                    }
            }
    }
}

bool cmp(edge e1,edge e2)
{
    return e1.cost<=e2.cost;
}
int main()
{
    int n,count=0;
    cin>>n;
    init(n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++){
                cin>>A[i][j];
        }
    }
    checkEdges(n);
    sort(e,e+M,cmp);
    for (int i=0; i<M; ++i)
    {
        if(is_same_set(e[i].src,e[i].dst))
        {
            continue;
        }
        unite(e[i].dst,e[i].src);
        count+=e[i].cost;
    }
    cout<<count<<endl;
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

class UnionFind {
private:
    int n;
    vector<int> uni;
public:
    UnionFind(int _n) {
        n = _n;
        uni.clear();
        uni.resize(n, -1);
    }
    int root(int x) {
        if (uni[x] < 0) return x;
        return uni[x] = root(uni[x]);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (uni[x] > uni[y]) swap(x, y);
        uni[x] += uni[y];
        uni[y] = x;
    }
    void print() {
        for (auto x : uni) cout << x << " ";
        cout << endl;
    }
};

template <typename T>
struct edge {
    int from, to;
    T cost;
    edge(){}
    edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}
    bool operator< (const edge& e) const {
        return cost == e.cost ? (from == e.from ? to < e.to : from < e.from) : cost < e.cost;
    }
};

template <typename T>
class Kruskal {
private:
    int n;
    vector<edge<T>> edges;
    UnionFind uf;
public:
    Kruskal(int _n) : n(_n), uf(UnionFind(n)) {}
    void addEdge(int _from, int _to, T _cost) {
        edges.emplace_back(_from, _to, _cost);
    }
    T calc() {
        sort(all(edges));
        T res = 0;
        for (auto &e : edges) {
            if (!uf.same(e.from, e.to)) {
                uf.unite(e.from, e.to);
                res += e.cost;
            }
        }
        return res;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    cin >> n;
    Kruskal<double> kr(n);
    rep(i, n) {
        rep(j, n) {
            double c;
            cin >> c;
            if (c == -1) c = 1e9;
            kr.addEdge(i, j, c);
        }
    }
    cout << (int)kr.calc() << endl;
}

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

class TEdge;
struct TNode
{
	int TreeIndex;
	std::set<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::set<const TEdge*>::const_iterator It = Connected.begin(); It != Connected.end(); ++It){
		(*It)->JoinTree(Index);
	}
	Connected.insert(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();
		std::cout << FEdges.size() << std::endl;
		++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;
}