Go: package main

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

//util
var sc = bufio.NewScanner(os.Stdin)

func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func printList(list []int) {
	n := len(list)
	buf := bufio.NewWriter(os.Stdout)
	for _, v := range list[0 : n-1] {
		buf.Write([]byte(fmt.Sprintf("%d ", v)))
	}
	buf.Write([]byte(fmt.Sprintf("%d\n", list[n-1])))
	buf.Flush()
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

//solve
const (
	MAX   = 100
	INFTY = (1 << 21)
	WHITE = 0
	GRAY  = 1
	BLACK = 2
)

//V: グラフの頂点全体の集合
//T: MSTに属する頂点の集合
var (
	n     int
	M     [MAX][MAX]int //重みを記録する隣接行列
	color [MAX]int
	p     [MAX]int //MSTにおける頂点の親を記録
	d     [MAX]int //Tに属する頂点と、V−Tに属する頂点を繋ぐ辺の中で、重みが最小のものを記録
)

func prim() int {
	var u, minv int
	//初期化
	for i := 0; i < n; i++ {
		d[i] = INFTY
		p[i] = -1
		color[i] = WHITE
	}

	d[0] = 0

	for {
		//頂点uを決めていく
		//つまり、Tに属する頂点と、V−Tに属する頂点を繋ぐ辺の中で、重みが最小のものを決める
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			//未訪問かつ、辺の重みが最小となるuを選ぶ
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK
		for v := 0; v < n; v++ {
			//未訪問かつ、辺が存在するとき
			if color[v] != BLACK && M[u][v] != INFTY {
				if d[v] > M[u][v] {
					d[v] = M[u][v]
					p[v] = u
					color[v] = GRAY
				}
			}
		}
	}

	sum := 0
	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += M[i][p[i]]
		}
	}
	return sum
}

func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {

		for j := 0; j < n; j++ {
			tmp := nextInt()
			if tmp == -1 {
				tmp = INFTY
			}
			M[i][j] = tmp
		}

	}

	fmt.Println(prim())

}

C++: #include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>

using namespace std;

struct edge {
    int from, to, cost;
};

int main() {
    int n;
    cin >> n;

    vector<edge> E;
    int cost;
    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            cin >> cost;
            if (0 <= cost) {
                E.push_back((edge){ i, j, cost });
            }
        }
    }

    bool used[100] = {};
    used[0] = true;

    int ret = 0;

    while (1) {
        int next = -1;
        int min_cost = INT_MAX;
        for (int i=0; i<(int)E.size(); ++i) {
            edge &e = E[i];
            if (used[e.from] && ! used[e.to] && e.cost < min_cost) {
                next = e.to;
                min_cost = e.cost;
            }
        }
        if (next == -1) break;
        used[next] = true;
        ret += min_cost;
    }

    cout << ret << endl;

    return 0;
}

C++: #include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
#define NIL -2000000001
#define INFTY 2000000001
#define MAX 101
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n = 0;
int adm[MAX][MAX];
int color[MAX];
int d[MAX], p[MAX];
queue<int> queueBfs;


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

  while (true) {
    int mincost = INFTY;
    int u; //訪問する頂点

    for (int i = 0; i < n; i++) {
      if (color[i] != BLACK && d[i] < mincost) {
        mincost = d[i];
        u = i;
      }
    }
    if (mincost == INFTY) break;
    sum += mincost;
    color[u] = BLACK;

    // u周りの頂点vの情報を入れる
    for (int v = 0; v < n; v++) {
      if (color[v] != BLACK && adm[u][v] != -1 && adm[u][v] < d[v]) {
        d[v] = adm[u][v];
        p[v] = u;
        color[v] = GRAY;
      }
    }
  }

  return sum;
}

int main() {
  scanf("%d", &n);
  for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++) {
      scanf("%d", &adm[i][j]);
    }
  }

  printf("%d\n", mst());
  
  return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<tuple>
using namespace std;

int n,m=0,tmp,p[110],ans=0,a,b,c; //m:辺の数
tuple<int,int,int> line[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(){
    cin>>n;
    init(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>tmp;
            if(j>i){
                if(tmp!=-1){
                    line[m]=make_tuple(tmp,i,j);
                    m++;
                }
            }
        }
    }
    sort(line,line+m);
    init(n);
    for(int i=0;i<m;i++){
        c=get<0>(line[i]);
        a=get<1>(line[i]);
        b=get<2>(line[i]);
        if(!(is_same_set(a,b))){
            unite(a,b);
            ans+=c;
        }
        //cout<<c<<a<<b<<endl;
    }
    cout<<ans<<endl;
}

C++: #include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;

struct Edge{
  int src,dst;
  int weight;
  Edge(int src,int dst,int weight):
    src(src),dst(dst),weight(weight){}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

bool operator < (const Edge &m,const Edge &n){
  return m.weight!=n.weight ? m.weight>n.weight :
    m.src!=n.src ? m.src>n.src : m.dst>n.dst;
}

struct UnionFind{
  vector<int> data;
  UnionFind(int size):
    data(size,-1){}

  int root(int x){
    return data[x]<0 ? x :
      data[x]=root(data[x]);
  }

  void unionset(int x,int y){ //bool->void
    x=root(x);y=root(y);
    if(x!=y){
      if(data[y]<data[x])
	swap(x,y);
      data[x]+=data[y];
      data[y]=x;
    }
    //return x!=y;
  }

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

/*test用関数
void PrintGraph(Graph);
void PrintEdges(Edges);
void PrintPriority_queue(priority_queue<Edge>);
*/

pair<int,Edges> MinimumSpinningForest(Graph g){
  int n=g.size();
  UnionFind uf(n);
  priority_queue<Edge> que;

  for(int i=0;i<n;i++){
    for(Edges::iterator l=g[i].begin();l!=g[i].end();l++){
      if((*l).src<(*l).dst && (*l).weight>0)
	que.push(*l);
    }
  }

  //PrintPriority_queue(que);
  int sum=0;
  Edges select;

  while((int)select.size()<n && !que.empty()){
    Edge tmp=que.top();que.pop();

    if(!uf.findset(tmp.src,tmp.dst)){
      uf.unionset(tmp.src,tmp.dst);
      select.push_back(tmp);
      sum+=tmp.weight;
    }
  }

  return pair<int,Edges>(sum,select);
}


int main(int argc,char* argv[]){
  Graph g;
  int n,x;
  pair<int,Edges> p;

  cin>>n; 
  for(int i=1;i<=n;i++){
    for(int l=1;l<=n;l++){
      cin>>x;
      Edge tmp(i,l,x);
      Edges input;input.push_back(tmp);
      g.push_back(input);
    }
  }

  //PrintGraph(g);

  p=MinimumSpinningForest(g);

  //PrintEdges(p.second);
  
  cout<<p.first<<endl;
  return 0;
}

C++: # include<iostream>
using namespace std;
const int MAX = 100;
const int INFTY = (1 << 21);
const int WHITE = 0;
const int GREY = 1;
const int 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] = INFTY;
		p[i] = -1;
		color[i] = WHITE;
	}

	d[0] = 0;

	while (1) {
		minv = INFTY;
		u = -1;
		for (int i = 0; i < n; i++) {
			if (color[i] != BLACK && minv > d[i]) {
				minv = d[i];
				u = i;
			}
		}

		if (u == -1) break;
		color[u] = BLACK;

		for (int v = 0; v < n; v++) {
			if (color[v] != BLACK && M[u][v] != INFTY) {
				if (d[v] > M[u][v]) {
					d[v] = M[u][v];
					p[v] = u;
					color[v] = GREY;
				}
			}
		}
	}

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

	return sum;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int e; cin >> e;
			M[i][j] = (e == -1) ? INFTY : e;
		}
	}

	cout << prim() << endl;

	return 0;
}