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++: #include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Edge{
  int cost, x, y;
};

bool operator < (Edge a, Edge b) {
  return a.cost < b.cost;
}

vector<int> UFtree;

int root(int i) {
  if(UFtree[i] == i) return i;
  return (UFtree[i] = root(UFtree[i]));
}

bool is_same_set(int i, int j) {
  return root(i) == root(j);
}

void unite(int i, int j) {
  UFtree[root(i)] = root(j);
}

int main() {
  int n, cost, w = 0;
  cin >> n;
  for(int i = 0; i < n; i++) UFtree.push_back(i);
  vector<Edge> Edges;
  Edge e;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
	cin >> cost;
	if(j > i && cost != -1) {
	  e.cost = cost; e.x = i; e.y = j;
	  Edges.push_back(e);
	}
    }
  }
  sort(Edges.begin(), Edges.end());
  for(int i = 0; i < Edges.size(); i++) {
    if(!is_same_set(Edges[i].x, Edges[i].y)) {
      w += Edges[i].cost;
      unite(Edges[i].x, Edges[i].y);
    }
  }
  cout << w << endl;
  return 0;
}

C++: #include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef vector <int> vi;
typedef vector <vi> vvi;

class blanch{
	public:
		int weight;
		int from;
		int to;
		blanch():
			weight(0),from(0),to(0){};
		blanch(int newweight, int newfrom, int newto):
			weight(newweight),from(newfrom),to(newto){};
};
typedef vector <blanch> vb;

bool operator<( const blanch &blanch1, const blanch &blanch2){
	return (blanch1.weight > blanch2.weight);
	}

bool operator>( const blanch &blanch1, const blanch &blanch2){
	return (blanch1.weight < blanch2.weight);
	}

int make_graph(vvi &graph, vi &stamp){
	int n=graph.size();
	for (int j=0; j<n; j++){
		for (int i=0; i<n; i++){
			cin>>graph[i][j];
		}
		stamp[j] = 0;
	}
	return 0;
}

int Minimum_Spanning_Tree(vvi &graph, vi &stamp){

	priority_queue<blanch, vb, less<vb::value_type> > pq;
	int n = graph.size(), p1=0, total=0;
	stamp[p1] = 1;

	while (p1!=-1){
		for (int p2=0; p2<n; p2++){
			int *tmp = &graph[p1][p2];
			if (*tmp!=-1 && stamp[p2]==0){
				pq.push(blanch(*tmp, p1, p2));
			}
		}
		p1 = -1;
		while (! pq.empty()){
			blanch tmp = pq.top();
			if (stamp[tmp.from]==1 && stamp[tmp.to]==0){
				p1 = tmp.to;
				stamp[p1] = 1;
				total += tmp.weight;
				pq.pop();
				break;
			}
			pq.pop();
		}
	}
	return total;
}

int main(void){

	int n;
	cin>>n;
	vvi G(n, vi(n));
	vi stamp(n);

	make_graph(G, stamp);

	cout<<Minimum_Spanning_Tree(G, stamp)<<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];

  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>
using namespace std;
#define MAX 100
#define INF 1 << 30
int n, A[MAX + 1][MAX + 1], d[MAX + 1];
bool vis[MAX + 1];

int prim(int s){
  int sum = 0;
  for ( int i = 1; i <= n; i++){
    d[i] = A[s][i];
    vis[i] = false;
  }
  d[s] = 0;
  vis[s] = true;

  while ( 1 ){
    int minCost = INF;
    for ( int i = 1; i<=n; i++){
      if ( minCost > d[i] && !vis[i]){
        minCost = d[i];
        s = i;
      }
    }

    if ( minCost == INF)break;

    sum += minCost;
    vis[s] = true;

    for ( int i = 1; i <= n; i++){
      if ( d[i] > A[s][i] && !vis[i]){
        d[i] = A[s][i];
      }
    }
  }

  return sum;
}

int main(){
  cin >> n;
  int a;
  for ( int i = 1; i <= n; i++){
    for ( int j = 1; j <= n; j++){
      cin >> a;
      A[i][j] = ( a == -1 ) ? INF : a;
    }
  }

  cout << prim(1) << endl;

  return 0;
}

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

int main(void){
	int n, min_edge, next_node, count, sum;
	scanf("%d", &n);
	std::vector<std::vector<int>> edges;
	std::vector<int> isUsed;
	edges.resize(n);
	isUsed.resize(n);
	for(int i=0;i<n;i++){
		isUsed[i]=-1;
		edges[i].resize(n);
		for(int j=0;j<n;j++){
			scanf("%d", &edges[i][j]);
		}
	}

	min_edge=3000;
	isUsed[0] = 1;
	count = 0;
	sum=0;
	while(count<4){
		for(int i=0;i<n;i++){
			if(isUsed[i]==1){
				for(int j=0;j<n;j++){
					if (isUsed[j]==-1 && edges[i][j]>-1 && edges[i][j]<min_edge){
						min_edge = edges[i][j];
						next_node = j;
					}
				}
			}
		}
		sum += min_edge;
		isUsed[next_node]=1;
		min_edge = 3000;
		count += 1;
	}
	printf("%d\n", sum);
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#define PII pair<int,int>
#define MPII(a,b) make_pair(a,b)
using namespace std;
class NODE
{
public:
	vector<PII> v;
	int index = 0;
};
class Tree
{
public:
	vector<int> V;
	int cost = 0;
};

int main()
{
	NODE* nodes;
	nodes = new NODE[101];
	Tree T;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int t;
			cin >> t;
			if (t != -1)
			{
				PII p = MPII(t, j);
				nodes[i].v.push_back(p);
			}
		}
		sort(nodes[i].v.begin(), nodes[i].v.end());
	}
	T.V.push_back(1);
	while (1)
	{
		if (T.V.size() == n+1)break;
		int mincost=INT_MAX;
		int addv=-1;
		int index;
		for (auto itr : T.V)
		{
			if (mincost >= nodes[itr].v[nodes[itr].index].first)
			{
				mincost = nodes[itr].v[nodes[itr].index].first;
				addv = nodes[itr].v[nodes[itr].index].second;
				index = itr;
			}
		}
		nodes[index].index++;
		T.V.push_back(addv);
		T.cost += mincost;
	}
	cout << T.cost << endl;
	delete[] nodes;
	return 0;
}