Go: package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	I int
	J int
	A int
}

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]int, n)
	edges := make([]Edge, 0, n*(n-1)/2)
	parents := make([]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&g[i][j])
			if g[i][j] >= 0 {
				edges = append(edges, Edge{i, j, g[i][j]})
			}
		}
		parents[i] = i
	}
	sort.SliceStable(edges, func(i, j int) bool { return edges[i].A >= edges[j].A })

	sum := 0
	num := 0
	for len(edges) > 0 && num < n-1 {
		edge := edges[len(edges)-1]
		edges = edges[:len(edges)-1]

		if same(edge.I, edge.J, &parents) {
			continue
		}
		union(edge.I, edge.J, &parents)
		sum += edge.A
		num += 1
	}
	fmt.Println(sum)
}



func root(id int, parents *[]int) int {
	if id == (*parents)[id] {
		return id
	}
	return root((*parents)[id], parents)
}

func union(i, j int, parents *[]int) {
	(*parents)[root(j, parents)] = (*parents)[root(i, parents)]
}

func same(i, j int, parents *[]int) bool {
	return root(i, parents) == root(j, parents)
}

C++: import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

@SuppressWarnings("unchecked")
class MinCostTree{

    int N;
    class Edge{
        int from,to;
        long w;
        Edge(int from,int to,long w){this.from=from;this.to=to;this.w=w;}
    }
    List<Edge> edges[];
    List<Edge> minedge[];
    void add_edge(int u,int v,long w){
        edges[u].add(new Edge(u,v,w));
        edges[v].add(new Edge(v,u,w));
    }
    MinCostTree(int N){
        this.N=N;
        edges = new ArrayList[N];
        minedge = new ArrayList[N];
        for(int i=0;i<N;++i)edges[i]=new ArrayList<>();
        for(int i=0;i<N;++i)minedge[i]=new ArrayList<>();
    }
    long mincost(){
        PriorityQueue<Edge> que = new PriorityQueue<>((a,b)->a.w<b.w ? -1:1);
        boolean used[] = new boolean[N];
        used[0]=true;
        long res = 0;
        for(Edge e : edges[0])que.add(e);
        while(!que.isEmpty()){
            Edge e = que.poll();
            if(used[e.to])continue;
            used[e.to]=true;
            minedge[e.from].add(e);
            res += e.w;
            for(Edge ed : edges[e.to])que.add(ed);
        }
        return res;
    }
}

class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        MinCostTree mct = new MinCostTree(n);
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                long a = scan.nextLong();
                if(i>j && a>0)mct.add_edge(i, j, a);
            }
        }
        System.out.println(mct.mincost());
    }
}

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

int v_num;
int adjM[MAX+1][MAX+1];

int PrimsAlgorithm() 
{
    int current_vertex;
    int color[v_num+1], min_edge[v_num+1], parent[v_num+1];

    // set init state
    for (int i = 0; i < v_num; ++i)
    {
        color[i] = WHITE;
        min_edge[i] = INF;
        parent[i] = -1;
    }

    min_edge[0] = 0;

    while (true) 
    {
        int min_cost = INF;
        // move to the minimum vertex which can be accessed 
        for (int i = 0; i < v_num; ++i) 
        {
            if (color[i] != BLACK && min_edge[i] < min_cost)
            {
                min_cost = min_edge[i];
                current_vertex = i;
            }
        }

        if (min_cost == INF) break;

        color[current_vertex] = BLACK;

        for (int i = 0; i < v_num; ++i) 
        {
            if (color[i] != BLACK && adjM[current_vertex][i] != -1)
            {
                if (adjM[current_vertex][i] < min_edge[i])
                {
                    min_edge[i] = adjM[current_vertex][i];
                    parent[i] = current_vertex;
                    color[i] = GRAY;
                }
            } 
        }
    }

    int sum = 0;
    for (int i = 0; i < v_num; ++i) 
    {
        if (parent[i] != -1) sum += adjM[i][parent[i]];
    }
    return sum;
}

int main() 
{
    int v;
    cin >> v_num;
    for (int i = 0; i < v_num; ++i) 
    {
        for (int j = 0; j < v_num; ++j)
        {
            cin >> v;
            adjM[i][j] = v != -1 ? v : INF;
        }
    }
    
    cout << PrimsAlgorithm() << endl;
}

C++: #include <iostream>

using namespace std;


class Graph{
private:

  int size;
  int **graph;
  int *state;

public:

  Graph(int size){
    int i;
    int j;
    this->size = size;
    this->state = new int[size];
    this->graph = new int*[size];
    for(i = 0;i < size;i++){
      this->graph[i] = new int[size];
    }
    for(i = 0;i < this->size;i++){
	this->state[i] = 0;
      }
  }

  ~Graph(){
    int i;
    for(i = 0;i < this->size;i++){
      delete[] this->graph[i];
    }
    delete[] this->graph;
  }

  int getMinimum(){
    int i;
    int j;
    int min;
    int res = 0;

    for(i = 0;i < this->size;i++){
      min = 0;

      for(j = 1;j < this->size;j++){
	if(this->graph[i][j] != -1 && this->state[j] == 0){
	  if(this->graph[i][j] <= this->graph[i][min] 
	     ||	this->graph[i][min] == -1){
	    min = j;
	  }
	}
      }

      if(state[min] == 0){
	state[min] = 1;
	res += graph[i][min];
      }
    }
    return res;
  }

  void setValue(int x,int y,int value){
    this->graph[x][y] = value;
  }

};

int main(){

  int i;
  int j;
  int n;
  int a;

  Graph *graph;

  cin >> n;

  graph = new Graph(n);

  for(i = 0;i < n;i++){
    for(j = 0;j < n;j++){
      cin >> a;
      graph->setValue(i,j,a);
    }
  }

  cout << graph->getMinimum() << endl;

  delete graph;

  return 0;
}

C++: #include <iostream>
#define NMAX 100
#define AMAX 2001

using namespace std;

enum state{
  WHITE,
  BLACK
};

int main(){
  int A[NMAX][NMAX];
  int n; cin>>n;
  state s[NMAX];
  
  for(int r=0;r<n;r++){
    for(int c=0;c<n;c++){
      cin>>A[r][c];
      if(A[r][c]==-1) A[r][c]=AMAX;
    }
  }

  for(int i=0;i<n;i++) s[i]=WHITE;
  s[0]=BLACK;
  
  int sum=0;

  while(1){
    bool flag=true;
    for(int i=0;i<n;i++){
      if(s[i]!=BLACK) flag=false;
    }
    if(flag) break;

    int min=AMAX;
    int minr,minc;
    for(int r=0;r<n;r++){
      for(int c=0;c<n;c++){
        if(s[r]==BLACK && s[c]!=BLACK && A[r][c]<min){
          min=A[r][c];
          minr=r;minc=c;
        }
      }
    }
    s[minr]=BLACK;s[minc]=BLACK; 
    sum+=min;
  }
  cout<<sum<<endl;
}

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

int main() {
	int num;
	std::cin >> num;

	std::vector<std::vector<int> > v(num);

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			int n;
			std::cin >> n;
			v[i].push_back(n);
		}
	}

	std::vector<int> n(v.size(), 0);
	std::vector<int> color(v.size(), 0);
	int count = 0, color_count = 1;
	for (int i = 1; i <= 2000; i++) {
		for (size_t j = 0; j < v.size(); j++) {
			for (size_t k = 0; k < v.size(); k++) {
				if (v[j][k] == i && ((color[k] == 0 || color[j] == 0) || (color[k] != color[j]))) {
					if (color[k] == 0) {
						if (color[j] != 0) {
							color[k] = color[j];
						} else {
							color[k] = color[j] = color_count;
							color_count++;
						}
					} else {
						if (color[j] == 0) {
							color[j] = color[k];
						} else {
							for (int l = 0; l < color.size(); l++) {
								if (color[l] == color[j]) {
									color[l] = color[k];
								}
							}
						}
					}
					count += i;
				}
			}
		}
	}

	std::cout << count << std::endl;

	return 0;
}