Go: package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	matrix   []int // 隣接行列
	minToMst int   // MSTへの重み最小値
	parent   int   // 最小値の相手
	color    color
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i].matrix = eAtoi((strings.Fields(eGetline(scanner))))
		nodes[i].parent = -1
		nodes[i].minToMst = math.MaxInt16
		nodes[i].color = white
	}

	// 初回はnode[0]がMSTに入るように,minToMstを設定
	nodes[0].minToMst = 0
	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか
		min := math.MaxInt16
		u := -1
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].minToMst < min {
				u = i
				min = nodes[i].minToMst
			}
		}

		if u == -1 {
			break
		}
		// MSTに追加する頂点決定
		nodes[u].color = mst

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みを更新
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].matrix[u] == -1 {
				// 接してない
				continue
			}
			if nodes[i].matrix[u] < nodes[i].minToMst {
				// node[u]との重みが最小
				nodes[i].minToMst = nodes[i].matrix[u]
				nodes[i].parent = u
			}
		}
	}

	sum := 0
	for _, v := range nodes {
		// node[0]はparentが入っていない
		if v.parent != -1 {
			sum += v.matrix[v.parent]
		}
	}
	fmt.Println(sum)
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

C++: #include<iostream>
#define N 100
#define INF 1000000
using namespace std;

int main(){
  int n,g[N][N],used[N]={},d[N]={},p[N];
  cin>>n;
  for(int i=0;i<n;i++){
    d[i]=INF,p[i]=-1;
    for(int j=0;j<n;j++){
      cin>>g[i][j];
      if(g[i][j]==-1) g[i][j]=INF;
    }
  }
  d[0]=0;
  
  while(1){
    int j=-1,min=INF;
    for(int i=0;i<n;i++)if(!used[i] && d[i]<min)min=d[i],j=i;
    if(j==-1) break;
    used[j]=1;
    for(int k=0;k<n;k++)
      if(!used[k] && g[j][k]!=INF)if(g[j][k]<d[k])d[k]=g[j][k],p[k]=j;
  }
int ans=0;
for(int i=0;i<n;i++)if(p[i]!=-1)ans+=g[i][p[i]];
cout<<ans<<endl;
 
 return 0;
}

C++: #include <algorithm>
#include <bitset>
#include <cassert>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <vector>
#include <array>
#include <chrono>
#include <random>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define VAR(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__);
template<typename T> void Scan(T& t) { std::cin >> t; }
template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { std::cin >> first; Scan(rest...); }
#define OUT(d) std::cout<<d;
#define FOUT(n, d) std::cout<<std::fixed<<std::setprecision(n)<<d;
#define SOUT(n, c, d) std::cout<<std::setw(n)<<std::setfill(c)<<d;
#define SP std::cout<<" ";
#define TAB std::cout<<"\t";
#define BR std::cout<<"\n";
#define FLUSH std::cout<<std::flush;
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& r:c)for(auto& i:r)std::cin>>i;
#define ALL(a) (a).begin(),(a).end()
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)
#define FORLL(i, a, b) for(ll i=ll(a);i<ll(b);++i)
#define RFORLL(i, a, b) for(ll i=ll(b)-1;i>=ll(a);--i)
#define REPLL(i, n) for(ll i=0;i<ll(n);++i)
#define RREPLL(i, n) for(ll i=ll(n)-1;i>=0;--i)
#define PAIR std::pair<int, int>
#define IN(a, x, b) (a<=x && x<b)
#define SHOW(d) {std::cout << #d << "\t:" << d << "\t";}
#define SHOWVECTOR(v) {std::cout << #v << "\t:";for(const auto& i : v){std::cout << i << " ";}std::cout << "\n";}
#define SHOWVECTOR2(v) {std::cout << #v << "\t:\n";for(const auto& i : v){for(const auto& j : i){std::cout << j << " ";}std::cout << "\n";}}
#define SHOWPAIRVECTOR2(v) {std::cout << #v << "\t:\n";for(const auto& i : v){for(const auto& j : i){std::cout<<'('<<j.first<<", "<<j.second<<") ";}std::cout << "\n";}}
#define SHOWPAIRVECTOR(v) {for(const auto& i:v){std::cout<<'('<<i.first<<", "<<i.second<<") ";}std::cout<<"\n";}
#define CHECKTIME(state) {auto start=std::chrono::system_clock::now();state();auto end=std::chrono::system_clock::now();auto res=std::chrono::duration_cast<std::chrono::nanoseconds>(end-start).count();std::cerr<<"[Time:"<<res<<"ns  ("<<res/(1.0e9)<<"s)]\n";}
#define SHOWQUEUE(a) {std::queue<decltype(a.front())> tmp(a);std::cout << #a << "\t:";for(int i=0; i<static_cast<int>(a.size()); ++i){std::cout << tmp.front() << "\n";tmp.pop();}std::cout << "\n";}

//#define int ll
using ll = long long;
using ull = unsigned long long;
constexpr int INFINT = 1 << 30;
constexpr ll INFLL = 1LL << 60;
constexpr double EPS = 0.0000000001;
constexpr int MOD = 1000000007;

//Union-Find
class UnionFind {
private:
	std::vector<int> parent;
	std::vector<int> height;

public:
	UnionFind(int size) : parent(size), height(size, 0) {
		REP(i, size) {
			parent[i] = i;
		}
	}
	void init(int size) {
		parent.resize(size);
		height.resize(size, 0);
		REP(i, size) {
			parent[i] = i;
		}
	}
	int find(int x) {
		if (parent[x] == x) {
			return x;
		}
		return parent[x] = find(parent[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (height[x] < height[y]) parent[x] = y;
		else parent[y] = x;
		if (height[x] == height[y]) ++height[x];
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

struct Edge {
	int from, to, cost;
	Edge(int f, int t, int c) : from(f), to(t), cost(c) {};
};
bool operator<(const Edge& l, const Edge& r) {
	return l.cost < r.cost;
}

signed main() {
	INIT;
	VAR(int, n);
	MAT(int, a, n, n);
	UnionFind uf(n);
	std::priority_queue<Edge> pq;
	REP(i, n) FOR(j, i + 1, n) {
		if (a[i][j] != -1) {
			pq.push(Edge(i, j, -a[i][j]));
		}
	}
	int ans = 0;
	while (!pq.empty()) {
		Edge now = pq.top(); pq.pop();
		if (uf.same(now.from, now.to)) continue;
		uf.unite(now.from, now.to);
		ans -= now.cost;
	}
	OUT(ans)BR;
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <string.h>

using namespace std;
typedef pair<int, int> P;
struct edge
{
	int to;
	int cost;
};

vector<edge> G[101];
bool isUsed[101];

void solve()
{
	int n;
	cin >> n;
	vector< vector<int> > data((n), vector<int>(n));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			int c;
			cin >> data[i][j];
		}
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j < n; ++j)
		{
			if (data[i][j] != -1)
			{
				edge e1, e2;
				e1.to = j;
				e1.cost = data[i][j];
				e2.to = i;
				e2.cost = data[j][i];
				G[i].push_back(e1);
				G[j].push_back(e2);
			}
		}
	}
	memset(isUsed, 0, sizeof(isUsed));
	int ans = 0;
	priority_queue < P, vector<P>, greater<P>> pque;
	pque.push(P(0, 0));
	while (!pque.empty())
	{
		P p = pque.top();
		pque.pop();
		int v = p.second;
		if (isUsed[v])
		{
			continue;
		}
		isUsed[v] = true;
		ans += p.first;
		for (int i = 0; i < G[v].size(); ++i)
		{
			edge e = G[v][i];
			pque.push(P(e.cost, e.to));
		}
	}
	cout << ans << endl;
}

int main()
{
	solve();
	return(0);
}