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>
using namespace std;
const int MAXN = 1000;
int main(void)
{
	int d[MAXN],a[MAXN][MAXN],vis[MAXN],p[MAXN];
	int n,ans = 0,cnt = 0;
	scanf("%d",&n);
	for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) scanf("%d",&a[i][j]);
	for(int i = 0;i < n;i++)
	{
		vis[i] = 0;
		p[i] = -1;
		d[i] = 2001;
	}
	d[0] = 0;
	while(true)
	{
		int u = -1,minv = 2001;
		for(int i = 0;i < n;i++)
		{
			if(d[i] < minv && !vis[i])
			{
				u = i;
				minv = d[i];
			}	
		}
		if(u == -1) break;
		cnt++;
		vis[u] = 1;
		for(int v = 0;v < n;v++)
		{
			if(!vis[v] && a[u][v] != -1)
			{
				if(d[v] > a[u][v])
				{
					d[v] = a[u][v];
					p[v] = u;
				}
			}
		}
	}
	for(int i = 0;i < n;i++) if(p[i] != -1) ans += a[i][p[i]];
	printf("%d\n",(cnt == n)?ans:-1);
	return 0;
}

C++: #if 0
????????£????????????1.5h
??¢?????????????????§??????????????¢??°????????£????????????sum????¨??????¨????????????????????£????????§?????????
???????????¢??????????????§????????????????????????????????????"-1"???????????????????????????????????§???????????§????????¨???????°???????????????????
#endif

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

int P[10000+10];

void init(int N){
	for(int i=0;i<=N;++i) P[i]=i;
}
int root(int a){
	if(P[a]==a)return a;
	else 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[j][i]; //???????????\???
		}
	}

	int M = 0; 
	int cost[N*N],src[N*N],dst[N*N];
	for (int r=0; r<N;r++)
		for (int c=0; c<r;c++) //r<c???????§?????????????
			if (A[r][c] > -1) {
				cost[M] = A[r][c];
				src[M] = r;
				dst[M] = c;
				M += 1;
			}
	pair<int,int> edges[2000+10];
	for(int i=0;i<M;i++)
		edges[i]=make_pair(cost[i],i); //first???????????????second???ID
	sort(edges,edges+M);
	
	//for(int i=0;i<M;++i)
		//cout<<edges[i].first<<endl;

	init(N);
	int sum=0;
	for(int i=0;i<M;i++){
		if(is_same_set(src[edges[i].second],dst[edges[i].second])==0){
			unite(src[edges[i].second],dst[edges[i].second]);
			sum+=edges[i].first;
		}
	}
		cout<<sum<<endl;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define REPR(i, m, n) for (int i = (int)(m); i >= (int)(n); i--)
#define all(v) v.begin(), v.end()
typedef long long ll;

using Graph = vector<vector<int> >;

int n, sum;
vector<bool> seen;
priority_queue<pair<int, int> > pq;

void dfs(const Graph &G, int v, int p){
  seen[v] = true;

  rep(u, n){
    if(u == p) continue;
    if(G[v][u] == -1) continue;
    pq.push(make_pair((-1)*G[v][u], u));
  }

  while(!pq.empty()){
    pair<int, int> tmp;
    tmp = pq.top();
    pq.pop();
    if(seen[tmp.second]) continue;
    sum += (-1)*tmp.first;
    int nv = tmp.second;
    p = v;
    dfs(G, nv, p);
  }

  return;
}

int main(){
  cin >> n;
  Graph G(n, vector<int>(n));
  rep(i, n) rep(j, n) cin >> G[i][j];

  seen.assign(n, false);
  sum = 0;
  dfs(G, 0, -1);

  cout << sum << endl;

  return 0;
}

C++: #include <iostream>
#include <utility>
#include <string>
#include <algorithm>
#include <set>
#include <deque>
#include <vector>
#define MAX 150
#define rep(i,p) for(int i=0;i<p;i++)
#define rep1(i,p) for(int i=1;i<=p;i++)
#define pb push_back
using namespace std;
int n,temp,a,b;
int A[MAX];
int B[MAX];
int W[MAX];
int V[MAX];
pair<int,int> edge[MAX];
int main(){
  cin >> n;
  rep(i,n) 
    rep(j,n) {
      int nnn = i*n + j;
      cin >> W[nnn];
      A[nnn] = i;
      B[nnn] = j;
      edge[nnn].first = W[nnn];
      edge[nnn].second = nnn;
  }
  // sort by lenght of edge
  sort(edge, edge+n*n);
  // printing
  // rep(i,n*n) {
  //   cout << A[edge[i].second] << " " << B[edge[i].second]
  //        << " " << edge[i].first << endl;;
  // }
  int sum = 0;
  rep(i,n) V[i] = i;
  rep(i,n*n) {
    if (edge[i].first == -1) continue;
    temp = edge[i].second;
    // a , b : vertex
    a = A[temp]; 
    b = B[temp];
    if (V[a] != V[b]) {
      // ?????????????????????
      sum += edge[i].first;
      if (V[a] != a && V[b] == b){
        V[b] = V[a];
      } else if (V[a] == a && V[b] != b) {
        V[a] = V[b];
      } else if (V[a] == a && V[b] == b) {
        V[b] = V[a];
      }
    } else {

    }
  }
  cout << sum << endl;
  return 0;
}

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

#define MAX_SIZE 110
#define INF (1<<30)
#define NOT_VISITED 0
#define VISITED 1
#define COMPLETE 2

int n, G[MAX_SIZE][MAX_SIZE];

int prim() {
    int d[MAX_SIZE], parent[MAX_SIZE], status[MAX_SIZE];
    for (int i = 0; i < n; i++) {
        d[i] = INF;
        parent[i] = -1;
        status[i] = NOT_VISITED;
    }
    d[0] = 0;

    int u, min_cost;
    while (1) {
        u = -1;
        min_cost = INF;
        for (int i = 0; i < n; i++) {
            if (min_cost > d[i] && status[i] != COMPLETE) {
                u = i;
                min_cost = d[i];
            }
        }
        if (u == -1) break;
        status[u] = COMPLETE;
        for (int i = 0; i < n; i++) {
            if (status[i] == COMPLETE || G[u][i] == INF) continue;
            if (d[i] > G[u][i]) {
                d[i] = G[u][i];
                parent[i] = u;
                status[i] = VISITED;
            }
        }
    }
    
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (parent[i] != -1) sum += G[i][parent[i]];
    }

    return sum;
}

int main() {
    cin >> n;

    int a;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a;
            if (a == -1) G[i][j] = INF;
            else G[i][j] = a;
        }
    }

    cout << prim() << endl;

    return 0;
}