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 INF = 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] = INF;
        p[i] = -1;
        color[i] = WHITE;
    }

    d[0] = 0;

    while(1){
        minv = INF;
        u = -1;

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

        if(u == -1) break;

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

    int sum = 0;

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

    return sum;
}

int main(){
    cin >> n;

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

    cout << prim() << endl;
    
    return 0;
}

C++: #include <iostream>
#include <string>
#define MAX_N 110
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
int cost[MAX_N][MAX_N], mincost[MAX_N];
bool used[MAX_N];
int prim(int n)
{
    int res = 0;
    mincost[0] = 0;
    while(true)
    {
        int v = -1;
        for(int u = 0; u < n; u++)
        {
            if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
        }
        if(v == -1) break;
        used[v] = true;
        res += mincost[v];
        for(int u = 0; u < n; u++) mincost[u] = min(mincost[u], cost[v][u]);
    }
    return res;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for(int i = 0; i < MAX_N; i++) used[i] = false;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> cost[i][j];
            if(cost[i][j] == -1) cost[i][j] = INF;
        }
        mincost[i] = INF;
    }
    int ans = prim(n);
    cout << ans << endl;
    return 0;
}

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]; // d:??±??? ,p:??????v?????? ,color:????????????

  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;

    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 <iostream>
#include <set>
using namespace std;

const int Max = 105;
const int INF = (1<<29);
int n, G[Max][Max], Min;
set<int> T;
set<int> V;

void Pime0(int u)
{
    T.insert(u);
    V.erase(u);
    set<int>::iterator i, j;
    while(T.size()<n)
    {
        int minv = INF;
        int index = -1;
        for(i=T.begin(); i!=T.end(); i++)
        {
            for(j=V.begin(); j!=V.end(); j++)
            {
                if(G[*i][*j]!=INF && minv>G[*i][*j])
                {
                    minv = G[*i][*j];
                    index = *j;
                }
            }
        }
        T.insert(index);
        V.erase(index);
        Min += minv;
    }
}
int main()
{
    cin >> n;
    Min = 0;
    for(int i=0; i<n; i++)
    {
        V.insert(i);
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> G[i][j];
            if(G[i][j]==-1)
                G[i][j] = INF;
        }
    }
    Pime0(0);
    cout << Min << endl;
    return 0;
}

C++: #include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int p[101];
void makeset(int N){
    for(int i=0;i<N;++i){
        p[i]=i;
    }
}
int root(int x){
    if(p[x]==x) return x;
    return (p[x]==root(p[x]));
}
void unite(int x,int y){
    p[root(x)]=root(y);
}
bool same(int x,int y){
    return root(x)==root(y);
}
int main(){
    int N,M=0;
    int A[101][101],cost[101],src[101],dst[101];
    cin>>N;
    makeset(N);
    for(int r=0;r<N;++r){
        for(int c=0;c<N;++c){
            cin>>A[r][c];
        }
        for(int c=r+1;c<N;++c){
            if(A[r][c]>-1){
                cost[M]=A[r][c];
                src[M]=r;
                dst[M]=c;
                M+=1;
            }
        }
    }
    pair<int,pair<int,int>>edges[101];
    for(int i=0;i<M;++i){
       edges[i]=make_pair(cost[i],make_pair(src[i],dst[i]));
    }
    sort(edges,edges+M);
    //for(int i=0;i<M;++i){
        //cout<<edges[i].first<<edges[i].second.first<<edges[i].second.second<<endl;
    //}
    int total=0,num=0,flag=0;
    for(int i=0;i<M;++i){
        //if(same(edges[i].second.first,edges[i].second.second)){continue;}
        //else{
            unite(edges[i].second.first,edges[i].second.second);
            total+=edges[i].first;
            num++;
            cout<<edges[i].first<<edges[i].second.first<<edges[i].second.second<<endl;
        //}
        if(num==N-1){
            flag=1;
            break;
        }
    }
    if(flag){
        cout<<total<<endl;
    }
}