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 <cstdio>
#define INF 1<<30

int n, M[100][100];

int prim() {
    int e, minv, minx, s;
    int p[n], d[n], v[n];

    for (e = 0; e < n; e++) {
        p[e] = -1;
        d[e] = INF;
        v[e] = 0;
    }

    d[0] = 0;

    while (1) {
        minv = INF;
        minx = -1;
        for (e = 0; e < n; e++) {
            if (minv > d[e] && v[e] != 1) {
                minx = e;
                minv = d[e];
            }
        }

        if (minx == -1) break;
        v[minx] = 1;
        
        for (e = 0; e < n; e++) {
            if (v[e] != 1 && M[minx][e] != INF) {
                if (d[e] > M[minx][e]) {
                    d[e] = M[minx][e];
                    p[e] = minx;
                }
            }
        }
    }

    s = 0;
    for (e = 0; e < n; e++) {
        if (p[e] != -1) s += M[e][p[e]];
    }

    return s;
}

int main(void) {
    int i, j, v;
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &v);
            M[i][j] = (v == -1) ? INF : v;
        }
    }

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

    return 0;
}

C++: #include "bits/stdc++.h"
 
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<VVLL> VVVLL;

#define SORT_ASC(c) sort((c).begin(), (c).end())
#define SORT_DESC(c) sort((c).begin(), (c).end(), greater<typeof((c).begin())>())
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define FORL(i,a,b) for(LL i=(a);i<(b);++i)
#define REPL(i,n)  FORL(i,0,n)
#define ALL(a) (a).begin(),(a).end()
 
const double EPS = 1e-10;
const double PI  = acos(-1.0);

 //debug func
template<typename T>
void vprint(vector<T> v) {
    for(auto x : v) {
        cerr << x << " ";
    }
    cerr << endl;
}
 
template<typename T>
void vvprint(vector<vector<T>> vv) {
    REP(i, vv.size()) {
        REP(j, vv[i].size()) {
            cerr << vv[i][j] << " ";
        }
        cerr << endl;
    }
}

template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Thomas Draper */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator itr1 = first;
   Iterator itr2 = last;
   ++itr1;
   if (last == itr1)
      return false;
   itr1 = last;
   --itr1;
   itr1 = k;
   --itr2;
   while (first != itr1)
   {
      if (*--itr1 < *itr2)
      {
         Iterator j = k;
         while (!(*itr1 < *j)) ++j;
         iter_swap(itr1,j);
         ++itr1;
         ++j;
         itr2 = k;
         rotate(itr1,j,last);
         while (last != j)
         {
            ++j;
            ++itr2;
         }
         rotate(k,itr2,last);
         return true;
      }
   }
   rotate(first,k,last);
   return false;
}

inline double get_time_sec(void){
    return static_cast<double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count())/1000000000;
}

template<typename T>
T lcm(T a, T b) {
    return (a / __gcd(a, b)) * b;
}

template<typename T>
map<T, T> prime_list(T n) {
    map<T, T> ret;
    for(T i = 2; i*i <= n; i++) {
        if(n % i == 0) {
            ret[i] = 0;
            while(n % i == 0) {
                n /= i;
                ret[i]++;
            }
        }
    }
    if(n != 1) ret[n]++;
    return ret;
}

#define MOD 1000000007

LL mypow(LL a, LL n) {
    if(n == 0) return 1;
    if(n == 1) return a % MOD;
    if(n % 2 == 1) return (a * mypow(a, n-1)) % MOD;
    LL t = mypow(a, n/2);
    return (t * t) % MOD; 
}

LL mycomb(LL n, LL k) {
    if(n == 0 || n == k) return 1;
    LL x = 1, y = 1;
    REP(i, k) {
        x = x * (n-i) % MOD;
        y = y * (i+1) % MOD;
    }
    return x * mypow(y, MOD - 2) % MOD;
}

#define INF 1e8

struct edge {int u, v, cost;};

vector<edge> g;
VI par, rnk;

int root(int x) {
    if(par[x] == x) return x;
    else return par[x] = root(par[x]);
}

int same(int x, int y) {
    x = root(x);
    y = root(y);
    return x == y;
}

void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if(rnk[x] > rnk[y]) {
        par[y] = x;
    } else {
        par[x] = y;
        if(rnk[x] == rnk[y]) rnk[y]++;
    }
}

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    int n;
    cin >> n;
    REP(i, n) {
        REP(j, n) {
            int c;
            cin >> c;
            if(c > -1) {
                edge e;
                e.u = i, e.v = j, e.cost = c;
                g.push_back(e);
            }
        }
    }
    int ans = 0;
    par = VI(n);
    iota(ALL(par), 0);
    rnk = VI(n, 1);
    auto cmp = [](edge x, edge y) {
        return x.cost < y.cost;
    };
    sort(ALL(g), cmp);
    REP(i, g.size()) {
        if(!same(g[i].u, g[i].v)) {
            unite(g[i].u, g[i].v);
            ans += g[i].cost;
        }
    }
    cout << ans << endl;
}