Go: package main

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

const (
	WHITE int = iota
	GRAY
	BLACK
)

type graph struct {
	G [][]int
	C []int
	D []int
	P []int
}

var INFTY = 1 << 32

func constructGraph() *graph {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	g := make([][]int, n)
	c := make([]int, n)
	d := make([]int, n)
	p := make([]int, n)

	for i := 0; i < n; i++ {
		sc.Scan()
		fields := strings.Fields(sc.Text())
		g[i] = toIntSlice(fields)
	}

	return &graph{g, c, d, p}
}

func (g *graph) initMst() {
	for i := 0; i < len(g.G); i++ {
		g.C[i] = WHITE
		g.D[i] = INFTY
	}
	g.D[0] = 0
	g.P[0] = -1
}

func (g *graph) primMst() int {
	g.initMst()

	var u int
	for {
		mincost := INFTY
		for i := 0; i < len(g.G); i++ {
			if g.C[i] != BLACK && g.D[i] < mincost {
				mincost = g.D[i]
				u = i
			}
		}

		if mincost == INFTY {
			break
		}

		g.C[u] = BLACK

		for i := 0; i < len(g.G); i++ {
			if g.C[i] != BLACK && g.existEdge(u, i) {
				if g.G[u][i] < g.D[i] {
					g.D[i] = g.G[u][i]
					g.P[i] = u
				}
			}
		}
	}

	totalCost := 0
	for _, cost := range g.D {
		totalCost += cost
	}
	return totalCost
}

func (g *graph) existEdge(u, v int) bool {
	return g.G[u][v] != INFTY && g.G[v][u] != INFTY
}

func toIntSlice(s []string) []int {
	a := make([]int, len(s))
	for i, v := range s {
		num, _ := strconv.Atoi(v)
		if num == -1 {
			num = INFTY
		}
		a[i] = num
	}
	return a
}

func main() {
	g := constructGraph()
	fmt.Println(g.primMst())
}

C++: #include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;

const int V_MAX = 10000;
const int INF = 100000000;

struct Edge {
	bool operator< (const Edge& e)const {
		return e.w > w;
	}
	int s;
	int t;
	int w;
};

int parent(int uft[], int child) {
	if (uft[child] == -1)return child;
	return uft[child] = parent(uft, uft[child]);
}

int main() {
	int v, e;
	vector<Edge> edge;
	int uft[V_MAX];
	int ans = 0;
	
	scanf("%d%d", &v, &e);
	for (int i = 0; i < v; i++) {
		uft[i] = -1;
	}
	for (int i = 0; i < e; i++) {
		Edge e;
		scanf("%d%d%d", &e.s, &e.t, &e.w);
		
		edge.push_back(e);
	}

	sort(edge.begin(), edge.end());

	for (int i = 0; i < e; i++) {
		Edge e = edge[i];
		
		int p1 = parent(uft, e.s);
		int p2 = parent(uft, e.t);
		if (p1 != p2) {
			uft[p1] = p2;
			ans += e.w;
		}
	}

	printf("%d\n", ans);

	return 0;
}

C++: //pair???????????¨???????????????????????£????????§31-179573????????????????????????????????????????????????????????????
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
using namespace std;

int P[10010];
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);
}

int main(){
  int n;
  cin>>n;
  int A[n][n];
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin >> A[i][j];
    }
  }
  vector<int> cost,src,dst;
  int M=0;
  for(int r=0;r<n;r++){
    for(int c=r+1;c<n;c++){
      if(A[r][c]>-1){
	cost[M]=A[r][c];
	src[M]=r;
	dst[M]=c;
	M+=1;
      }
    }
  }
  pair<int,int> edges[M];
  for(int i=0;i<M;i++){
    edges[i] =make_pair(cost[i],i);
  }

  sort(edges,edges+M);
  int s=0;
  for(int i=0;i<M;i++){
    int k= edges[i].second;
    int p=src[k];
    int q=dst[k];
    if(is_same_set(p,q)) continue;
    unite(p,q);
    s+=edges[i].first;
  }
  cout << s<<endl;
}

C++: #include<bits/stdc++.h>

using namespace std;

struct Edge{
    int from,to,w;
    bool friend operator < (const Edge& a,const Edge& b){
        return a.w<b.w;
    }
};
const int maxn=105;
vector<Edge> G;
int fa[maxn];
int V,E;
void init(){
    for(int i=1;i<=V;i++)
        fa[i]=i;
}

int find(int x){
    int y=fa[x];
    for(;fa[y]!=y;y=fa[y]);
    while(x!=y){
        int temp=fa[x];
        fa[x]=y;
        x=temp;
    }
    return y;
}

void merge(int x,int y){
    int nx=find(x);
    int ny=find(y);
    if(nx!=ny){
        fa[nx]=ny;
    }
}
int ans=0;
void krusal(int v){
    sort(G.begin(),G.end());
    E=G.size();
    V=v;
    init();
    for(int i=0;i<E;i++){
        Edge temp=G[i];
        int fa1=find(temp.from);
        int fa2=find(temp.to);
        if(fa1!=fa2){
            ans+=temp.w;
            fa[fa1]=fa2;
        }
    }
}

int main(){
    int V;
    cin>>V;
    E=0;
    for(int i=1;i<=V;i++){
        for(int j=1;j<=V;j++){
            int key;
            cin>>key;
            if(key!=-1){
                G.push_back(Edge{i,j,key});
            }
        }
    }
    krusal(V);
    cout<<ans<<endl;
}

C++: #include <iostream>
#include <vector>
#include <queue>
#define to first
#define cost second
const int inf=1e9+7;
using namespace std;
int main(){

  int n,tmp,r=0,now=0,flag[100]={};
  cin>>n;
  vector <pair<int,int> > gl[n];
  priority_queue < pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > >q;

  for(int i=0;i<n;i++) for(int j=0;j<n&&cin>>tmp;j++) if(tmp!=-1) gl[i].push_back(make_pair(j,tmp));
  for(int j=0;j<n-1;j++){
    for(int i=0;i<gl[now].size();i++) if(!flag[gl[now][i].to]) q.push(make_pair(gl[now][i].cost,gl[now][i].to));
    flag[now]=1;
    for(;flag[q.top().second];) q.pop();
    r+=q.top().first;
    now=q.top().second;
    q.pop();
  }
  cout<<r<<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(T _from, T _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;
}