Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

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

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	seen := make([]bool, n)
	for i := range list {
		list[i] = make([]int, n)
		for j := range list[i] {
			list[i][j] = scanInt()
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	sum := 0
	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if seen[node.id] {
			continue
		}
		seen[node.id] = true
		sum += node.weight

		for i, w := range list[node.id] {
			if w < 0 {
				continue
			}
			heap.Push(h, Node{id: i, weight: w})
		}
	}

	fmt.Println(sum)
}

C++: #include <bits/stdc++.h>

using namespace std;
using LL = long long;
using P = pair<int, int>;
using Tapris = tuple<int, int, int>;

#define REP(i, n) for(LL i = 0; i < n; ++i)
#define FOR(i, a, n) for(LL i = a; i < n; ++i)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e15;
const int MOD = 1e9 + 7;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

//#define int long long

class UnionFind {
    private:
        vector<int> parent;  // 親
        vector<int> rank;    // 木の深さ
    public:
        UnionFind(int n);          // n要素で初期化
        int Find(int x);           // 木の根を返す
        void Unite(int x, int y);  // xとyの属する集合を併合
        bool Same(int x, int y);   // xとyが同じ集合に属するか否か
};

UnionFind::UnionFind(int n) : parent(vector<int>(n)), rank(vector<int>(n)) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

int UnionFind::Find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return parent[x] = Find(parent[x]);
    }
}

void UnionFind::Unite(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;

    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}

bool UnionFind::Same(int x, int y) { return Find(x) == Find(y); }

template <typename T>
struct Edge {
    int src, to;
    T cost;
    Edge(int to, T cost) : src(-1), to(to), cost(cost) {}
    Edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
};

template <typename T>
class Kruskal {
    private:
        int V; // 頂点数
        vector<Edge<T>> edges;
        vector<vector<Edge<T>>> minimumSpanningTree;
    public:
        Kruskal(int n);
        void AddEdge(int from, int to, T cost);
        T Run();
        vector<vector<Edge<T>>> GetMinimumSpanningTree();
};

template <typename T>
Kruskal<T>::Kruskal(int n) : V(n), minimumSpanningTree(n) {}

template <typename T>
void Kruskal<T>::AddEdge(int from, int to, T cost) {
    edges.push_back(Edge<T>(from, to, cost));
}

template <typename T>
T Kruskal<T>::Run() {
    sort(edges.begin(), edges.end(), [](const Edge<T> &a, const Edge<T> &b){
        return a.cost < b.cost;
    });
    UnionFind tree(V);
    T total = 0;
    
    for(auto &e : edges){
        if(!tree.Same(e.src, e.to)){
            tree.Unite(e.src, e.to);
            total += e.cost;
            minimumSpanningTree[e.src].push_back(Edge<T>(e.to, e.cost));
            minimumSpanningTree[e.to].push_back(Edge<T>(e.src, e.cost));
        }
    }

    return total;
}

template <typename T>
vector<vector<Edge<T>>> Kruskal<T>::GetMinimumSpanningTree(){
    return minimumSpanningTree;
}

/*************** using variables ***************/

/**********************************************/

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    Kruskal<int> kruskal(n);
    REP(i, n){
        REP(j, n){
            int x;
            cin >> x;
            if(x != -1) kruskal.AddEdge(i, j, x);
        }
    }

    cout << kruskal.Run() << endl;
}

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

struct Edge{
  int to,cost;
  bool operator<(const Edge&a)const{
    return cost>a.cost;
  }
};
struct Graph{
  Graph(int n):E(n),T(n),N(n){}
  vector<vector<Edge>>E,T;
  int N;
  void add_edge(int a,int b,int c){
    E[a].push_back({b,c});
    E[b].push_back({a,c});
  }
  void prim(int s){
    bool visited[N];
    priority_queue<pair<Edge,int>>Q;
    memset(visited,0,N);
    Q.push({{s,0},-1});
    while(!Q.empty()){
      Edge e=Q.top().first;
      int from=Q.top().second;Q.pop();
      if(visited[e.to])continue;
      visited[e.to]=1;
      if(from+1)T[from].push_back(e),T[e.to].push_back({from,e.cost});
      for(auto&a:E[e.to])
      if(!visited[a.to])Q.push({a,e.to});
    }
  }
  int get_cost(){
    int ret=0;
    for(auto&a:T)for(auto&b:a)ret+=b.cost;
    return ret/2;
  }
  vector<Edge>* get_MST(){
    return T.data();
  }
};

main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin>>N;
    Graph G(N);
    for(int i=0;i<N;++i)
        for(int j=0;j<N;++j){
            int a;
            cin>>a;
            if(~a) G.add_edge(i,j,a);
        }
    G.prim(0);
    cout<<G.get_cost()<<endl;
}

C++: #include <iostream>
using namespace std;
static const int MAX=100;
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;
static const int INF=1<<21;

int n;
int A[MAX][MAX];

int prim(){
  int i,color[MAX],d[MAX],p[MAX],mincost,k,sum;
  for(i=0;i<n;i++){
    color[i]=WHITE;
    d[i]=INF;
  }
  d[0]=0;
  p[0]=-1;

  while(1){
    mincost=INF;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && d[i]<mincost){
	mincost=d[i];
	k=i;
      }
    }
    if(mincost==INF) break;
    color[k]=BLACK;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && A[k][i]!=INF){
	if(A[k][i]<d[i]){
	  d[i]=A[k][i];
	  p[i]=k;
	  color[i]=GRAY;
	}
      }
    }
  }
  sum=0;
  for(i=0;i<n;i++){
    if(p[i]!=-1){
      sum+=A[i][p[i]];
    }
  }
  return sum;
}

int main(){
  int i,j,a;
  cin>>n;

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

  cout<<prim()<<endl;

  return 0;
}