Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	g := make([][]int, n)
	ans := make([][]int, n)

	inf := 1 << 30
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		ans[i] = make([]int, n)
		for ii := 0; ii < n; ii++ {
			g[i][ii] = getNextInt(scanner)
			if g[i][ii] == -1 {
				g[i][ii] = inf
			}
			ans[i][ii] = -1
		}
	}

	im := make(IntMap, 1)

	im.increment(1)

	for len(im) < n {
		min := inf
		u := -1
		v := -1
		for i := range im {
			for ii := 0; ii < n; ii++ {
				if im.get(ii) != 0 {
					continue
				}
				if min > g[i][ii] {
					min = g[i][ii]
					u = i
					v = ii
				}
			}
		}
		im.increment(v)
		ans[u][v] = min
		ans[v][u] = min
	}

	sum := 0
	for i := 0; i < n-1; i++ {
		for ii := i + 1; ii < n; ii++ {
			if ans[i][ii] != -1 {
				sum += ans[i][ii]
			}
		}
	}

	fmt.Fprintln(writer, sum)
	writer.Flush()
}

// IntMap ...
type IntMap map[int]int

func (m IntMap) get(key int) int {
	if _, ok := m[key]; ok {
		return m[key]
	}
	return 0
}
func (m IntMap) increment(key int) {
	if _, ok := m[key]; ok == false {
		m[key] = 0
	}
	m[key]++
}

C++: #include <iostream>
#include <climits>
using namespace std;
#define MAX 100
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n,d[MAX+10],p[MAX+10],color[MAX+10];
int W[MAX+10][MAX+10];

int prim()
{
  int v,k,mini,flag,u=0;
  for(int i=0;i<n;i++)
  {
      d[i]=INT_MAX;
      p[i]=-1;
  }
  d[0]=0;
  while(1)
  {
      mini=INT_MAX;
      flag=1;
      for(int i=0;i<n;i++)
      {
          if(d[i]<mini&&color[i]!=BLACK)
          {
              u=i;
              mini=d[i];
              flag=0;
          }
      }
      if(flag) break;
      color[u]=BLACK;
      for(v=0;v<n;v++)
      {
          if(W[u][v]!=INT_MAX&&color[v]!=BLACK)
          {
            if(d[v]>W[u][v])
            {
              d[v]=W[u][v];//更新当前点到最小生成树的距离
              p[v]=u;//每一轮都需要跑更新前驱结点
            }
          }
      }
  }
  int sum=0;
  for(int i=0;i<n;i++)
  {
      if(p[i]!=-1) sum+=W[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;
         W[i][j]=(e==-1)?INT_MAX:e;
        }
        color[i]=WHITE;
    }
    cout<<prim()<<endl;
}

C++: #include <stdio.h>
#include <iostream>
#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;

class edge
{
  public:
    int i, j, weigt;
    bool operator()(edge e1, edge e2)
    {
        return e1.weigt < e2.weigt;
    }
};
edge e[10000];
int main()
{
    int n;
    cin >> n;
    int b[n][n] = {};
    int k = 0;
    int tmp = 0;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> tmp;
            if (j < i + 1 || tmp < 0)
                continue;
            e[k].i = i;
            e[k].j = j;
            e[k].weigt = tmp;
            k++;
        }
    }
    sort(e, e + k, edge());
    for (int i = 0; i < k; i++)
    {
        if (b[e[i].i][e[i].j] == 0)
        {
            cout << e[i].weigt << "\n";
            sum += e[i].weigt;
            b[e[i].i][e[i].j] = 1;
            b[e[i].j][e[i].i] = 1;
            for (int j = 0; j < n; j++)
            {
                if (b[e[i].i][j] == 1 || b[e[i].j][j] == 1)
                    b[e[i].i][j] = b[e[i].j][j] = b[j][e[i].i] = b[j][e[i].j] = 1;
            }
        }
    }
    cout << sum << "\n";
    return 0;
}

C++: #include <iostream>
#include <limits.h>
using namespace std;

int main(void)
{
	int n, now = 0, flag[101];
	long ans = 0, an[100][100], min[100];

	cin >> n;

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cin >> an[i][j];
		}
		min[i] = LONG_MAX - 1;
		flag[i] = 0;
	}

	do {
		flag[now] = 1;
		flag[100] = 0;

		for(int j = 0; j < n; j++) {
			if(an[now][j] != -1 && an[now][j] < min[j] && flag[j] == 0) {
				min[j] = an[now][j];
			}
		}

		int key = LONG_MAX - 1, key_j;

		for(int j = 0; j < n; j++) {
			if(flag[j] == 0 && min[j] < key) {
				key = min[j];
				key_j = j;
			}
		}

		now = key_j;
		ans += key;

		for(int i = 0; i < n; i++) {
			if(flag[i] == 1) {
				flag[100]++;
			}
		}
	
	}while(flag[100] != n - 1);

	cout << ans << endl;

	return 0;
}

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

int n;					//えぬ
int a[100][100] = {0};	//辺の重さ
int f[100] = {0};		//その頂点がすでに連結済みかどうか、その集団の番号
int c = 0;				//全体の重さ
int d = 1;				//次につける集団番号
int s = 0;				//選んだ本数
vector<int> w;			//木のリスト、軽いもの順
int wc = 0;				//見てる木のリストの位置

int main(){
	cin >> n;
	//まず辺の重さをaに入れる
	//wに辺のリストを入れる
	for ( int i = 0; i < n; i++ ) {
		for ( int j = 0; j < n; j++ ) {
			cin >> a[i][j];
			if ( a[i][j] != -1 && i < j ) w.push_back( a[i][j] );
		}
	}
	sort( w.begin(),w.end() );
	while(true) {									//n-1本選ぶまで無限ループ
		for ( int i = 0; i < n - 1; i++ ) {			// i < j を満たすように木を調べ続ける
			for ( int j = i + 1; j < n; j++ ) {
				if ( a[i][j] != w[wc] ) continue;	//その木が一番軽い木だったらそれを対象に検査を始める
				if ( f[i] > 0 && f[j] > 0 ) {		//その木の両端が両方とも連結済みだったら
					if ( f[i] != f[j] ) {
						int y = f[j];
						for ( int x = 0; x < n; x++ ) {
							if ( f[x] == y ) f[x] = f[i];
						}
						c += a[i][j];
						s++;
					}
				}else if ( f[i] == 0 && f[j] == 0 ) {
					f[i] = d;
					f[j] = d;
					d++;
					c += a[i][j];
					s++;
				}else {
					if ( f[i] == 0 ) {
						f[i] = f[j];
						c += a[i][j];
						s++;
					}else {
						f[j] = f[i];
						c += a[i][j];
						s++;
					}
				}
				wc++;
				a[i][j] = -1;
				if ( s == n-1 ) break;
			}
			if ( s == n-1 ) break;
		}
		if ( s == n-1 ) break;
	}
	cout << c << endl;
	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

#define Vi vector<int>
#define FOR(i,s,e) for (int i=s; i<e; i++)
#define ITER(v) v.begin(), v.end()

constexpr int N_MAX = 100;

int weight[N_MAX][N_MAX];

int mst(const int n) {
    bool ismember[n] = {false};
    Vi members;

    members.push_back(0);
    ismember[0] = true;
    int cost = 0;

    FOR(t,1,n) {
        int addcost = -1;
        int newmember = -1;
        for (const int i : members)
        FOR(j,0,n) {
            if (ismember[j]) { continue; }
            const int w = weight[i][j];
            if (w < 0) { continue; }
            if (addcost < 0 || addcost > w) {
                addcost = w;
                newmember = j;
            }
        }
        members.push_back(newmember);
        ismember[newmember] = true;
        cost += addcost;
        //cout << "#" << newmember << endl;
    }
    return cost;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    FOR(i,0,n) {
        FOR(j,0,n) {
            cin >> weight[i][j];
        }
    }

    int cost = mst(n);
    cout << cost << endl;

    return 0;
}