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 <iostream>
using namespace std;
#define MAX 100
#define INFINITY (1<<30)
enum{
	white=0,
	gray=1,
	black=2,
};

int n,m[MAX][MAX];

int prim(){
	int u,minv;
	int d[MAX],p[MAX],color[MAX];
	for(int i=0;i<n;i++){
		d[i]=INFINITY;
		p[i]=-1;
		color[i]=white;
	}
	d[0]=0;
	while(1){
		minv=INFINITY;
		u=-1;
		for(int i=0;i<n;i++){
			if(minv>d[i]&&color[i]!=black){
				u=i;
				minv=d[i];
			}
		}
		if(u==-1)	break;
		color[u]=black;
		for(int v=0;v<n;v++){
			if(color[v]!=black&&m[u][v]!=INFINITY){
				if(d[v]>m[u][v]){
					d[v]=m[u][v];
					p[v]=u;
					color[v]=gray;
				}
			}
		}
	}
	int sum=0;
	for(int i=0;i<n;i++){
		if(p[i]!=-1)	sum+=m[i][p[i]];
	}
	return sum;
}

int main(){
	cin>>n;
	int e;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>e;
			if(e==-1)	m[i][j]=INFINITY;
			else	m[i][j]=e;
		}
	}
	cout<<prim()<<endl;
	return 0;
}