Go: package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

type ElementKey int
type Node struct {
	key    ElementKey
	parent *Node
	rank   int
}

func newNode(key ElementKey) *Node {
	node := Node{}
	node.key = key
	node.parent = &node
	node.rank = 0

	return &node
}

func union(x, y *Node) {
	xSet := findSet(x)
	ySet := findSet(y)
	link(xSet, ySet)
}

func link(x, y *Node) {
	if x.rank > y.rank {
		y.parent = x
	} else {
		x.parent = y

		if x.rank == y.rank {
			y.rank++
		}
	}
}

func findSet(x *Node) *Node {
	if x != x.parent {
		x.parent = findSet(x.parent)
	}
	return x.parent
}

func newDisjointSets(nSets int) *DisjointSets {
	sets := DisjointSets{}
	sets.keyToNode = map[ElementKey]*Node{}
	for i := 0; i < nSets; i++ {
		key := ElementKey(i)
		sets.keyToNode[key] = newNode(key)
	}
	return &sets
}

type DisjointSets struct {
	keyToNode map[ElementKey]*Node
}

func (sets *DisjointSets) union(x, y ElementKey) {
	xNode := sets.keyToNode[x]
	yNode := sets.keyToNode[y]
	union(xNode, yNode)
}

func (sets DisjointSets) findSet(x ElementKey) *Node {
	xNode := sets.keyToNode[x]
	return findSet(xNode)
}

type Edge struct {
	i, j   int
	weight int
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	sets := newDisjointSets(n)
	edges := []Edge{}
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, n)
		for j := 0; j < n; j++ {
			a[i][j] = nextInt()
			if a[i][j] >= 0 {
				e := Edge{
					i:      i,
					j:      j,
					weight: a[i][j],
				}
				edges = append(edges, e)
			}
		}
	}
	sort.Slice(edges, func(i, j int) bool { return edges[i].weight < edges[j].weight })
	totalWeight := 0
	for _, edge := range edges {
		i := ElementKey(edge.i)
		j := ElementKey(edge.j)
		if sets.findSet(i) != sets.findSet(j) {
			totalWeight += edge.weight
			sets.union(i, j)
		}
	}
	fmt.Println(totalWeight)
}

C++: /** ???????????????, ??¢??°?????¨??? **/
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

// ?????\?????????
// ?????°:?????????????´???°, ??????
// ???????????°????????§?????????????????´?£????????????´??????
// Down: ??????, Up: ??????
void insertionSortDown(int *a, int N){
    for(int i=1; i<N; i++){
        //???????????????,???????????????????´?????????????????????¨??????
        int v = a[i];
        int j = i - 1;

        //????????????????????¨?????¨??????????????????. ?????´??????????????????.
        while(j >= 0 && a[j] > v){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = v;

        /**
        cout << to_string(i) << "??????" << endl;
        for(int k=0; k<N; k++){
            cout << a[k] << endl;
        }
         **/
    }
}

void insertionSortUp(int *a, int N){
}

// ??????????????????
// ???????????´?£????????????´??????. ?????????????????°return?????????int???????????´??????
void bubbleSortUp(int *a, int N){
    int sw = 0;
    int flag = 1;

    while(flag == 1){
        flag = 0;

        for(int j=N-1; j>=sw; j--){
            if(a[j-1] > a[j]){
                swap(a[j-1], a[j]);
                flag = 1;
            }
        }
        sw++;
        //???????????´???????????????????????¨????????¨???????????£??????????????§.
    }
}

void selectionSortUp(int *a, int N){
    for(int i=0; i<N-1; i++){
        int minj = i;

        for(int j=i; j<N; j++){
            if(a[minj] > a[j]){
                minj = j;
            }
        }
        swap(a[minj], a[i]);
        //???????????´??§??????????????°??????????????????????????????,???????°????????????????????´???¨??????????????????
    }
}

// ?????¢??¢?´¢ O(nq)
// ??????, ?????????????´???°, ?????????????????????
bool linearSearch(int *a, int n,int key){
    int i = 0;
    a[n] = key; //??????????????????????????????

    while(a[i] != key) i++;

    //????´?????????????????????§??????????????°true?????????
    return i != n;
}



#define V_MAX 100
#define INFTY 5000
#define WHITE 0
#define GRAY 1
#define BLACK 2


int M[V_MAX][V_MAX];
int d[V_MAX], p[V_MAX];
int n;
int color[V_MAX];

int Prim(int u){
    p[u] = -1; //p??????????????????????¨????

    for(int i=0; i<n; i++){
        d[i] = INFTY;
        p[i] = -1;
        color[i] = WHITE;
    }

    d[u] = 0; //d?????????????????????

    while(1){
        int mincost = INFTY;
        int from = -1;

        //??????????????§???????°?????????¨??????????¨???¶????????????
        for(int i=0; i<n; i++){
            if(color[i] != BLACK && d[i] < mincost){
                mincost = d[i];
                from = i;
            }
        }

        if(from == -1) break;

        color[from] = BLACK;

        for(int v=0; v<n; v++){
            if(color[v] != BLACK && M[from][v] != INFTY){
                if(M[from][v] < d[v]){
                    d[v] = M[from][v];
                    p[v] = from; //???????¨??????????
                    color[v] = GRAY;
                }
            }
        }
    }

    int sum = 0;

    for(int j=0; j<n; j++){
       if(p[j] != -1) sum += M[j][p[j]];
    }

    return sum;
}

int main(){

    cin >> n;

    for(int k=0; k<n; k++) color[k] = WHITE;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int tmp;
            cin >> tmp;
            if(tmp != -1) M[i][j] = tmp;
            else M[i][j] = INFTY;
        }
    }

    int sum = Prim(0);

    cout << sum << endl;
}

C++: //minimum spanning tree
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_ 12_A&lang=jp
//右　奥

#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;


int P[10010]; // 0 から 10000 までの頂点を取り扱い可能
void init(int N) { // 初期化 はじめは全ての頂点はバラバラ
  for (int i=0; i<N; i++) P[i] = i;
}
int root (int a) { //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);
}


int main(){
  int n;
  cin >> n;
  tuple<int,int,int> cost[10010]; //Array for cost
  int count = 0;
  for (int i = 0; i < n; i ++){
    for (int j = 0; j < n; j++){
      int t;
      cin >> t;
      if (t >= 0){
      get<1>(cost[count]) = i;
      get<2>(cost[count]) = j;
      get<0>(cost[count]) = t;
      count++;
    }
    }
  } // tupleに行列Aの情報を入れる
  sort(cost,cost + n*n);//sortする //n*n個ソートするときの書き方

  init(n + 10); // 初期化 はじめは全ての頂点はバラバラ

  int ans = 0;
  int anscount = 0; //このcountがnになった時点で終了する
  int k = 0;
  while (anscount != n-1){
    if (is_same_set(get<1>(cost[k]), get<2>(cost[k]))) {
      k ++; //get<1>(cost[k]), get<2>(cost[k])の親が同じときkを１増やす
    }
    else{
      unite(get<1>(cost[k]), get<2>(cost[k])); //合同じゃなければ合同にする（なぜならsortによって最小値から返されるから）
      ans += get<0>(cost[k]);
      k++;
      anscount++;
    }
  }


  cout << ans << endl;
  return 0;
}