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>
#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;
	
}