Go: package main

import (
	"sort"
	"bufio"
	"os"
	"fmt"
	"strconv"
)

// Define disjoint-set forests

type vertexNo int

type vertex struct {
	number vertexNo
	rank int
	parent *vertex
}

func makeSet(number vertexNo) vertex {
	return vertex {
		number: number,
		rank: 0,
		parent: nil,
	}
}

func union(x, y *vertex) *vertex {
	return link(findSet(x), findSet(y))
}

func link(x, y *vertex) *vertex {
	if x.rank > y.rank {
		y.parent = x
		return x
	} else {
		x.parent = y
		if x.rank == y.rank {
			y.rank += 1
		}
		return y
	}
}

func findSet(v *vertex) *vertex {
	if v.parent == nil {
		return v
	}
	v.parent = findSet(v.parent)
	return v.parent
}

// Function to calculate minimum spanning tree

type matrix [][]int

type edge struct {
	one vertexNo
	two vertexNo
	weight int
}

const(
	MAX_VERTICES = 100
)

func newEdgesFromMatrix(matrix matrix) []edge {
	edges := make([]edge, 0, MAX_VERTICES * MAX_VERTICES)

	for i := 0; i < len(matrix); i++ {
		row := matrix[i]
		for j := i; j < len(row); j++ {
			if row[j] >= 0 {
				edge := edge{one: vertexNo(i+1), two: vertexNo(j+1), weight: row[j]}
				edges = append(edges, edge)
			}
		}
	}

	return edges
}

func solve(matrix matrix) int {
	nVertices := len(matrix)

	// initialize vertices
	vertices := make([]vertex, nVertices)
	for i := 0; i < nVertices; i++ {
		vertices[i] = makeSet(vertexNo(i+1))
	}

	// prepare edges sorted in the ascending order of weight
	edges := newEdgesFromMatrix(matrix)
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})

	unionCount := 0
	weightSum := 0
	for unionCount < nVertices-1 {
		for i := 0; i < len(edges); i++ {
			edge := edges[i]
			v1 := &vertices[edge.one-1]
			v2 := &vertices[edge.two-1]
			rep1 := findSet(v1)
			rep2 := findSet(v2)
			if rep1.number == rep2.number {
				continue
			}
			union(rep1, rep2)
			edges = append(edges[0:i], edges[i+1:]...)
			weightSum += edge.weight
			unionCount++
			break
		}
	}

	return weightSum
}

// main

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	matrix := parseMatrix(n, sc)

	edges := newEdgesFromMatrix(matrix)
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})

	fmt.Println(solve(matrix))
}

func parseMatrix(n int, sc *bufio.Scanner) [][]int {
	matrix := make([][]int, n)
	for i := 0; i < n; i++ {
		matrix[i] = make([]int, n)
		for j := 0; j < n; j++ {
			x, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			matrix[i][j] = x
		}
	}
	return matrix
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextInt(sc *bufio.Scanner) (int, error) {
	return strconv.Atoi(nextText(sc))
}

C++: // clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever while (true)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
using namespace std;
// clang-format on

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(const int &s = 0, const int &d = 0, const Weight &w = 0) : src(s), dst(d), weight(w) {}
};

using Edges = std::vector<Edge>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

class Graph {
  std::vector<Edges> g;

public:
  Graph(const int &size = 0) : g(size) {}

  void addArc(const int &src, const int &dst, const Weight &w = 1) { g[src].emplace_back(src, dst, w); }

  void addEdge(const int &node1, const int &node2, const Weight &w = 1) {
    addArc(node1, node2, w);
    addArc(node2, node1, w);
  }

  const Edges &operator[](const int &i) const { return g[i]; }

  Graph toRootedTree(int r);
  std::pair<std::vector<Weight>, std::vector<int>> dijkstra(const int &src, const int &inf);
  Matrix warshallFloyd(const int &inf);
  std::pair<Weight, Edges> prim(const int &r);
  template<typename UnionFind> std::pair<Weight, Edges> kruskal();
  Weight solveTSP(const int &inf);
};

std::pair<Weight, Edges> Graph::prim(const int &r = 0) {
  struct comp {
    bool operator()(const Edge &e, const Edge &f) const { return e.weight > f.weight; }
  };
  Edges tree;
  Weight total = 0;
  std::vector<int> vs(g.size());
  std::priority_queue<Edge, std::vector<Edge>, comp> q;
  q.emplace(-1, r, 0);
  while (q.size()) {
    Edge e = q.top();
    q.pop();
    if (vs[e.dst]) continue;
    vs[e.dst] = true;
    total += e.weight;
    if (e.src != -1) tree.emplace_back(e);
    for (auto &f : g[e.dst]) {
      if (!vs[f.dst]) q.emplace(f);
    }
  }
  return {total, tree};
}

main {
  int n;
  cin >> n;
  Graph g(n);
  rep(i, n) rep(j, n) {
    int a;
    cin >> a;
    if (a >= 0) g.addArc(i, j, a);
  }
  cout << g.prim().first << endl;
}

C++: #include<iostream>
#include<vector>
using namespace std;

enum color{WHITE, GRAY, BLACK};

int calc(vector<vector<int> >& G, vector<color>& state){
    int i_min = 0;
    int j_min = 0;
    for (int i = 0; i < G.size(); i++) {
        if (state[i] == WHITE || state[i] == BLACK) {
            continue;
        }
        bool is_black = true;
        for (int j = 0; j < G[i].size(); j++) {
            if (state[j] == WHITE){
                is_black = false;
                if (G[i][j] < G[i_min][j_min]) {
                    i_min = i;
                    j_min = j;
                }
            }
        }
        if (is_black) state[i] = BLACK;
    }
    state[j_min] = GRAY;
    return G[i_min][j_min];
}

int Prim(vector<vector<int> >& G) {
    vector<color> state(G.size(), WHITE);
    state[0] = GRAY;
    int ret = 0;

    for (int i = 0; i < G.size() - 1; i++) {
        ret += calc(G, state);
    }
    return ret;
}

int main(){
    int n;
    cin >> n;
    vector<vector<int> > G(n, vector<int>(n));
    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] = 1e6;
        }
    }

    cout << Prim(G) << endl;

    return 0;
}

C++: #include<cstdio>
#include<iostream>
using namespace std;
int visited[101], d[101], adj[101][101];
int n;
const int INFTY = (1<<30);
void prim()
{
  for(int i=0; i<n; i++)
  {
    visited[i] = 0; d[i] = INFTY;
  }
  d[0] = 0;
  while(1)
  {
    int mincost = INFTY; int u= -1;
    for(int i=0; i<n; i++)
    {
      if(mincost > d[i] && visited[i] == 0)
      {
        mincost = d[i];
        u = i;
      }
    }
    if (mincost == INFTY) break;
    visited[u] = 1;
    for(int i=0; i<n; i++)
    {
      if(adj[u][i] != -1 && visited[i] == 0)
      {
        if(d[i] > adj[u][i])
          d[i] = adj[u][i];
      }
    }
  }
  int sum=0;
  for(int i=0; i<n; i++)
  {
    sum += d[i];
  }
  printf("%d\n", sum);
}
int main()
{
  //int n;
  scanf("%d", &n);
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
      scanf("%d", &adj[i][j]);

  prim();
  return 0;
}