Go: package main

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

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	matrix   []int // 隣接行列
	minToMst int   // MSTへの重み最小値
	parent   int   // 最小値の相手
	color    color
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i].matrix = eAtoi((strings.Fields(eGetline(scanner))))
		nodes[i].parent = -1
		nodes[i].minToMst = math.MaxInt16
		nodes[i].color = white
	}

	// 初回はnode[0]がMSTに入るように,minToMstを設定
	nodes[0].minToMst = 0
	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか
		min := math.MaxInt16
		u := -1
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].minToMst < min {
				u = i
				min = nodes[i].minToMst
			}
		}

		if u == -1 {
			break
		}
		// MSTに追加する頂点決定
		nodes[u].color = mst

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みを更新
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].matrix[u] == -1 {
				// 接してない
				continue
			}
			if nodes[i].matrix[u] < nodes[i].minToMst {
				// node[u]との重みが最小
				nodes[i].minToMst = nodes[i].matrix[u]
				nodes[i].parent = u
			}
		}
	}

	sum := 0
	for _, v := range nodes {
		// node[0]はparentが入っていない
		if v.parent != -1 {
			sum += v.matrix[v.parent]
		}
	}
	fmt.Println(sum)
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

C++: #include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static 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(minv>d[i] && color[i] != BLACK)
      {
        u=i;
        minv=d[i];
      }
    }

    // 全部黒だったらループ終了
    if(u==-1)break;

    color[u] = BLACK;

    // u番目とつながるものに値を与える(黒以外)
    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] = 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;
  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;
}

C++: #include<cstdio>
#include<vector>
#define N_MAX 105
#define INF 32700
using namespace std;
short adj[N_MAX][N_MAX];
struct Node{
    char parent;//父节点
    short weight;//权值
    bool state;//节点状态
}nodes[N_MAX];
char n;
int solve() {
    int res = 0;
    nodes[0].weight = 0;
    nodes[0].parent = -1;
    nodes[0].state = true;
    char nowParent = 0;
    while(true) {
        for(char j = 0; j < n; j++) {
            if(nodes[j].weight > adj[nowParent][j]&&!nodes[j].state) {
                nodes[j].weight = adj[nowParent][j];
            }
        }
        char minId = n;
        for(char i = 0; i < n; i++) {
            if(!nodes[i].state) {
                if(nodes[i].weight < nodes[minId].weight) {
                    minId = i;
                }
            }
        }
        if(minId == n) break;
        else nodes[minId].state = true;
        nodes[minId].parent=nowParent;
        nowParent=minId;
    }
    for(char i = 0; i < n; i++) {
        res += nodes[i].weight;
    }
    return res;
}

int main(){
    freopen("D:/works/C++200/try132_AOJ_ALDS1_12_A/data.txt", "r", stdin);
    scanf("%d", &n);
    for(char i=0;i<n;i++){
        for(char j=0;j<n;j++){
            scanf("%d", &adj[i][j]);
            if(adj[i][j]==-1) adj[i][j]=INF;
        }
        nodes[i].weight=INF;//初始权值
    }
    nodes[n].weight=INF;
    printf("%d\n", solve());
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

#define INF (1<<29)

int G[100][100], n;

int prim(){
  int p[100], d[100], c[100];
  int u;

  for(int i = 0; i < n; i++){
    d[i] = INF;
    p[i] = -1;
    c[i] = 0;
  }

  d[0] = 0;

  while(1){
    int minv = INF;
    u = -1;
    for(int i = 0; i < n; i++){
      if(minv > d[i] && c[i] != 2){
        u = i;
        // cout << u << endl;
        minv = d[i];
      }
    }

    if(u == -1) break;
    c[u] = 2;
    for(int v = 0; v < n; v++){
      if(c[v] != 2 && G[u][v] != INF){
        if(d[v] > G[u][v]){
          d[v] = G[u][v];
          p[v] = u;
          c[v] = 1;
        }
      }
    }
  }

  int sum = 0;
  for(int i = 0; i < n; i++){
    if(p[i] != -1) sum+=G[i][p[i]];
    // cout << p[i] << endl;
  }
  return sum;
}


  int main(){

    cin >> n;
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        int v;
        cin >> v;
        G[i][j] = v;
        if(v == -1) G[i][j] = INF;
      }
      // cout << endl;
    }

    cout << prim() << endl;

  }

C++: #include <iostream>
#include <queue>

using namespace std;

using pii = pair<int, int>;

struct Graph{
  int v_size;
  vector<vector<pii>> adj;
  
  Graph(const int v_size):v_size(v_size){
    this->adj.resize(v_size);
  }
  
  void add_edge(const int s, const int t, const int w){
    this->adj[s].emplace_back(pii(t, w));
  }
};

int mst(const Graph& g){
  constexpr int INF{INT_MAX};
  
  vector<int> d(g.v_size, INF);
  priority_queue<pii, vector<pii>, greater<pii>> pq;

  d[0] = 0;
  pq.push(pii(0, 0));

  int ans {0};
  
  while(!pq.empty()){
    auto cost {pq.top().first};
    auto v {pq.top().second};
    pq.pop();

    if(d[v] < cost) continue;

    ans += cost;
    d[v] = -INF;

    for(int i = 0; i < g.adj[v].size(); ++i){
      auto to {g.adj[v][i].first};
      auto next_cost {g.adj[v][i].second};

      if(d[to] > next_cost){
        d[to] = next_cost;
        pq.push(pii(next_cost, to));
      }
    }
  }

  return ans;
}

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

  int x;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      cin >> x;
      if(x != -1){
        g.add_edge(i, j, x);
      }
    }
  }

  cout << mst(g) << endl;
}

C++: /*
* @Author: Samson
* @Date:   2018-06-12 18:24:44
* @Last Modified by:   Samson
* @Last Modified time: 2018-06-13 12:00:22
*/
//   @URL : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_A
#include<bits/stdc++.h>
#include<algorithm>
#include <cstdlib>
#define white 0
#define gray 1
#define black 2
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int MAXN = 1e3+10;

int p[MAXN],color[MAXN],a[MAXN][MAXN],t,n,d[MAXN];

int prim()
{
	int minv,u,v;
	for(int i = 1; i <= n; ++i)
	{
		d[i] = INF;
		p[i] = -1;
		color[i] = white;
	}
	
	d[1] = 0;

	while(1)
	{
		minv = INF;
		u = -1;
		for(int i = 1; i <= n; ++i)
		{
			if(minv > d[i] && color[i] != black)
				minv = d[i],u = i;
		}
		if(u == -1)	break;
		color[u] = black;
		for(int v = 1; v <= n; ++v)
		{
			if(color[v] != black && a[u][v] != INF)
			{
				if(d[v] > a[u][v])
				{
					d[v] = a[u][v];
					p[v] = u;
					color[v] = gray;
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; ++i)
		if(p[i] != -1)
			ans += a[i][p[i]];
	return ans;
}

int main(void)
{
	ios::sync_with_stdio(false); 
	//cin.tie(0);
	cin>>n;
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
		{
			cin>>t;
			a[i][j] = t==-1?INF:t;
		}
	}
	cout<<prim()<<'\n';
	return 0;
}