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<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
const ll MOD = (ll)1e9+7;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}

class minimum_spanning_tree{
public:
	int n;
	vvector<pll> edges;
	minimum_spanning_tree(int N):n(N){
		edges.resize(n);
	}

	void add_edge(int from, int to, ll cost){
		edges[from].emplace_back(to, cost);
	}

	ll solve(){
		ll res = 0;
		priority_queuer<pll> pq;
		pq.emplace(0, 0);
		vector<bool> used(n, false);
		while(pq.size()){
			pll d = pq.top();
			pq.pop();
			if(used[d.second]){
				continue;
			}
			used[d.second] = true;
			res += d.first;
			foreach(i, edges[d.second]){
				if(used[i.first])continue;
				pq.emplace(i.second, i.first);
			}
		}
		return res;
	}
};


int main(){
	int n;
	cin >> n;
	minimum_spanning_tree msp(n);
	rep(i, n){
		rep(j, n){
			int cost;
			cin >> cost;
			if(cost==-1)continue;
			msp.add_edge(i, j, cost);
		}
	}
	cout << msp.solve() << endl;
	return 0;
}

C++: #include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

struct Wside{
	int vertex;
	int weight;
	Wside(int a, int b){
		vertex=a; weight=b;
	}
};

vector<Wside>* info;
vector<int> scanned;
int n;
int minimum;

bool isScanned(int v){
	for(int i=0,sz=scanned.size(); i<sz; ++i){
		if(v==scanned[i]) return 1;
	}
	return 0;
}

int scan(){
	int temp_min=100000;
	int temp_v = 0;
	for(int i=0, sz=scanned.size(); i<sz; ++i){
		int s=scanned[i];
		for(int j=0, sz2=info[s].size(); j<sz2; ++j){
			if(isScanned(info[s][j].vertex)){
				continue;
			}
			temp_min = temp_min<info[s][j].weight? temp_min: info[s][j].weight;
			temp_v = temp_min<info[s][j].weight? temp_v: info[s][j].vertex;
		}
	}

	minimum += temp_min;
	scanned.push_back(temp_v);
	return 0;
}

int main()
{
	scanf("%d",&n);
	info = new vector<Wside> [n];

	int temp;
	for(int i=0; i<n; ++i){
		for(int j=0; j<n; ++j){
			scanf("%d",&temp);
			if(temp!=-1){
				info[i].push_back(Wside(j, temp));
			}
		}
	}

	scanned.push_back(0);
	while(scanned.size()!=n){
		scan();
	}
	cout << minimum << endl;

	delete[] info;

	return 0;
}

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

int n;
int cost[1000010],src[10010],dst[10010];
int a[110][110];
int P[10010];
int M;
class edges{
public:
    int x;
    int y;
    int costs;
}edges[1000010];
bool comp(class edges a,class edges b)
{
    return a.costs<b.costs;
}
void init(int N) {
    for (int i=1; i<=N; ++i)
        P[i] = i;
}

int root(int a) {
    if (P[a] == a)
        return a;
    return (P[a] = root(P[a]));
}

bool same(int a, int b) {
    return root(a) == root(b);
}

void unite(int a, int b) {
    P[root(a)] = root(b);
}

void inits(){
    for(int r=0;r<n;r++){
        for(int c=r+1;c<n;c++){
            if(a[r][c]>-1){
                cost[M]=a[r][c];
                src[M]=r;
                dst[M]=c;
                M++;
            }
        }
    }
    for(int i=0;i<M;i++){
        edges[i].x=src[i];
        edges[i].y=dst[i];
        edges[i].costs=cost[i];
}
    sort(edges,edges+M,comp);
}
int solve()
{
    int sum=0;
    for(int i=0;i<M;i++){
        if(same(edges[i].x,edges[i].y))
            continue;
        unite(edges[i].x,edges[i].y);
        sum+=edges[i].costs;
    }
    return sum;
}

int main(){
    cin>>n;
    init(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
        cin>>a[i][j];
    }
    inits();
    cout<<solve()<<endl;
    return 0;
}

C++: #include <iostream>

#define INF 10000

using namespace std;

int main(){
  int n; cin >> n;
  int G[n+1][n+1];
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin >> G[i][j];
    }
  }
  //prim's algorithm
  int d[n+1],visited[n+1];
  int sum=0;
  for(int i=1;i<=n;i++){
    visited[i]=0;
    d[i]=INF;
  }
  d[1]=0;
  while(1){
    int mincost=INF;
    int u;
    for(int i=1;i<=n;i++){
      if(visited[i]==0 && d[i]<mincost){
        mincost=d[i];
        u=i;
      }
    }
    if(mincost==INF) break;
    visited[u]=1;
    sum=sum+mincost;
    //update d
    for(int v=1;v<=n;v++){
      if(visited[v]==0 && G[u][v]!=-1){
        if(G[u][v]<d[v]){
          d[v]=G[u][v];
        }
      }
    }
  }
  cout << sum << endl;
}

C++: #include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
using namespace std;

int main(){
	
	int n;
	cin>>n;
	vector<vector<int>> a(n);
	rep(i,n){
		a[i].resize(n);
		rep(j,n){
			cin>>a[i][j];
			if(a[i][j]==-1)a[i][j]=INF;
		}
	}
	vector<int> t(n);
	rep(i,n){
		t[i]=0;
	}
	t[0]=1;
	int ans=0;
	rep(ii,n-1){
		int m=100000;
		int pm;
		rep(i,n){
			rep(j,n){
				if(t[i]==1 && t[j]==0 && m>a[i][j]){
					m=a[i][j];
					pm=j;
				}
			}
		}
		t[pm]=1;
		ans+=m;
	}
	cout<<ans<<endl;
	
}

C++: #include<iostream>
#include<cstdio>
#include<cstring>
#define MAX 2000200
#define MIN -2000000300
#define INF 1<<30
using namespace std;
int n;
int A[1000][1000];
int d[1000];
bool used[1000];

void Init(int n){
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      A[i][j] = INF;
    }
  }
}

int prime(){
  for(int i=0;i<n;i++){
    d[i] = INF;
    used[i]=false;
  }
  int ans=0;
  d[0] = 0;

  while(true){
    int v = -1;
    for(int i=0;i<n;i++){
      if(!used[i] && (v == -1 || d[v] > d[i]))v = i;
    }
    if(v == -1)break;
    ans+=d[v];
    used[v] = true;   

    for(int i=0;i<n;i++){
      d[i] = min(d[i],A[v][i]);
    }

  }
  return ans;
}

int main(){
  scanf("%d",&n);
  //  Init(n);
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      scanf("%d",&A[i][j]);
      if(A[i][j] == -1)A[i][j] = INF;
    }
  }
 
  printf("%d\n",prime());
 

  return 0;
}