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 <bits/stdc++.h>



using namespace std;



static const int INF = 99999;



int main(){



	int n,array[100][100];



	cin>>n;



	for(int i=0; i<n; i++){

		fill(array[i],array[i]+n,INF);

	}



	for(int i=0; i<n; i++){

		for(int j=0; j<n; j++){

			int tmp;

			cin>>tmp;

			if(tmp!=-1) array[i][j]=tmp;

		}

	}



	int ans=INF;

	

	for(int k=0; k<n; k++){

		bool flag[100];

		fill(flag,flag+n,false);

		flag[k]=true;



		int tmp=0;

		while(1){

			int u=-1,minv=INF;

			for(int i=0; i<n; i++){

				if(!flag[i]) continue;

				for(int j=0; j<n; j++){

					if(!flag[j] && array[i][j]<=minv){

						minv = array[i][j];

						u = j;

					}	

				}

			}

			if(minv==INF){

				break;

			}else{

				tmp += minv;

				flag[u]=true;

			}

		}

		ans = min(ans,tmp);

	}



	cout<<ans<<endl;



	return 0;

}

C++: #include <bits/stdc++.h>
using namespace std;
struct edge{
	int v,w;
	edge(){;}
	edge(int v,int w):v(v),w(w){;}
	bool operator<(const edge&p)const{
		return w>p.w;
	}
};
vector<edge> e[105];
priority_queue<edge> q;
bool ok[105];
int main(){
//	freopen("a.txt","r",stdin);
	int n,tem;
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			cin>>tem;
			if(tem!=-1)e[i].push_back(edge(j,tem)),e[j].push_back(edge(i,tem));
		}
	int res=0;
	ok[0]=1;
	int k=0;
	for(int i=0;i<e[0].size();i++)q.push(e[0][i]);
	while(k!=n-1){
		edge te=q.top();q.pop();
		if(ok[te.v])continue;
		else{
			k++;
			ok[te.v]=1;
			res+=te.w;
			for(int i=0;i<e[te.v].size();i++)q.push(e[te.v][i]);
		}
	}
	cout<<res<<endl;
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
struct edge {
    edge() {};
    edge(int s, int e, int d) : start {s}, end {e}, d {d} {};
    bool operator<(edge y){
        return d < y.d || start < y.start || end < y.end;
    };
    bool operator>(edge y){
        return d > y.d || start > y.start || end > y.end;
    };
    bool operator==(edge y){
        return d == y.d || start == y.start || end || y.end;
    };
    int start;
    int end;
    int d;
};

void dfs(vector<vector<int>> graph, bool* used, int id, int n){
    used[id] = true;
    for(int i = 0; i < n; ++i){
        if(graph[id][i] != -1 || used[i]){
            continue;
        }
        dfs(graph, used, i, n);
    }
}

bool is_connected(vector<vector<int>>& graph){
    int n = graph.size();
    bool used[n];
    for(int i = 0; i < n; ++i){
        used[i] = false;
    }
    dfs(graph, used, 0, n);
    for(int i = 0; i < n; ++i){
        if(!used[i]){
            return false;
        }
    }
    return true;
}

void delete_edges(vector<vector<int>>& graph){
    int edges_num = 0;
    vector<edge> vec {};
    int n = graph.size();
    for(int i = 0; i < n; ++i){
        for(int j = i+1; j < n; ++j){
            if(graph[i][j] != -1){
                ++edges_num;
                vec.push_back(edge(i, j, graph[i][j]));
            }
        }
    }
    sort(vec.begin(), vec.end(), [](edge x, edge y){
            return y.d < x.d;
         });

    for(auto it = vec.begin(); it != vec.end(); ++it){
        edge e = *it;
        graph[e.start][e.end] = -1;
        graph[e.end][e.start] = -1;
        if(is_connected(graph)){
            --edges_num;
            if(edges_num == n-1){
                return;
            }
        } else {
            graph[e.start][e.end] = e.d;
            graph[e.end][e.start] = e.d;
        }
    }
}

vector<vector<int>> gen_spanning_tree(vector<vector<int>>& graph){
    vector<vector<int>> tree {graph};
    delete_edges(tree);
    return tree;

}

int calc_weight(vector<vector<int>> graph){
    int sum = 0;
    int n = graph.size();
    for(int i = 0; i < n; ++i){
        for(int j = i+1; j < n; ++j){
            if(graph[i][j] == -1){
                continue;
            }
            sum += graph[i][j];
        }
    }
    return sum;
}

int main(){
    int n;
    cin >> n;
    vector<vector<int>> graph {n, vector<int>(n, 0)};
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> graph[i][j];
        }
    }
    auto tree = gen_spanning_tree(graph);
    cout << calc_weight(tree) << endl;
}

C++: #include<bits/stdc++.h>
using namespace std;
#define MAX 100
#define INF 1<<25
int n,cost[MAX][MAX];
int mincost[MAX];
bool used[MAX];
int prim(){
  for(int i=0;i<n;i++)mincost[i]=INF,used[i]=false;
    mincost[0]=0;
  int res=0;
  while(1){
    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]=1;
    res+=mincost[v];
    for(int u=0;u<n;u++)mincost[u]=min(mincost[u],cost[v][u]);
  }
return res;
}
int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      int e;
      cin>>e;
      cost[i][j]=(e==-1)?INF:e;
    }
  }
  cout<<prim()<<endl;
}