Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

const INF = 1 << 60

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	G := make([][]int, N)
	for i := 0; i < N; i++ {
		G[i] = make([]int, N)
		for j := 0; j < N; j++ {
			G[i][j] = sc.nextInt()
		}
	}
	d := make([]int, N)
	for i := 0; i < N; i++ {
		d[i] = INF
	}
	seen := make([]bool, N)
	d[0] = 0
	ans := 0
	for {
		cur := 0
		minCost := INF
		for i := 0; i < N; i++ {
			if !seen[i] && d[i] < minCost {
				minCost = d[i]
				cur = i
			}
		}
		if minCost == INF {
			break
		}
		seen[cur] = true
		ans += d[cur]
		for i := 0; i < N; i++ {
			cost := G[cur][i]
			if cost != -1 && cost < d[i] {
				d[i] = cost
			}
		}
	}

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}

C++: #include<vector>
#include<algorithm>
#include<queue>
#include<stdio.h>
using namespace std;
//结点数最大值 
const int maxn = 1000;
//结点权值最大值 
const int INFTY = 1000000;
//first是下一个结点位置,second是权值 
vector< pair<int,int> > g[maxn];
//parent是父节点,d是当前最短边,is是是否使用过 
int parent[maxn],d[maxn],is[maxn];
//结点数 
int n;
//初始化函数 
void Init(){
	for(int i = 0;i<n;++i){
		//父节点全设置为不存在 
		parent[i] = -1;
		//全设置为最大距离 
		d[i] = INFTY;
		//为输入边和权值做好准备 
		g[i].clear();
		//初始化各边使用状态 
		is[i] = false;
	}
}
int prim(){
	//最小生成树总权值 
	int ans = 0;
	//存储边 
	priority_queue< pair<int,int> >q;
	pair<int,int> work;
	//将0起点的存进去 
	for(int i = g[0].size()-1;i>=0;--i){
		work= g[0][i];
		parent[work.first] = 0;
		//最大堆变最小堆 
		work.second*=-1;
		swap(work.first,work.second);
		q.push(work);
	}
	is[0] = true;
	
	while(q.size()){
		work = q.top();q.pop();
		//to是结点号,v是权值 
		int to = work.second,v = -1*work.first;
		//距离过大或者目标节点已被标记则略过 
		if(d[to]<to||is[to])continue;
		is[to] = true;
		//展示选择的边 
		//printf("%d --> %d:%d\n",parent[to],to,v);
		ans+=v;
		//将当前结点to的边加进队列 
		for(int i  = g[to].size()-1;i>=0;--i){
			work= g[to][i];
			//如果权值比当前的还要大或者目标结点已经被标记过了则跳过 
			if(is[work.first]||d[work.first]<work.second)continue;
			parent[work.first] = to;
			work.second*=-1;
			swap(work.first,work.second);
			q.push(work);
		}
	}
	return ans;
}
int main(){
	int m,a,b,c;
	scanf("%d",&n);
	Init();
	for(int i = 0;i<n;++i){
		for(int j = 0;j<n;++j){
		scanf("%d",&a);
		if(a==-1)continue; 
		g[i].push_back(make_pair(j,a));
		}
	}
	printf("%d\n",prim());
	return 0;
}
//test:
/*
6 10
0 1 2
0 3 1
1 3 3
1 2 1
1 4 2
3 2 2
3 5 2
2 4 5
2 5 3
4 5 1
*/

C++: #define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define USE_LLONG_AS_INT
#ifdef USE_LLONG_AS_INT
#define int long long
#define inf (1ll<<60)
#else
#define inf (1<<30)
#endif
#define rep(i,n) for(int i=0;i<(n);i++)
#define Rep(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

int n;
vvi g;

int prim(){
    vi d(n,inf),p(n,-1);
    d[0]=0;
    vector<bool> b(n);
    while(true){
        int u;
        int m=inf;
        rep(i,n){
            if(m>d[i]&&!b[i]){
                u=i;
                m=d[i];
            }
        }
        if(m==inf)break;
        b[u]=true;
        rep(v,n){
            if(!b[v]&&g[u][v]!=inf){
                if(d[v]>g[u][v]){
                    d[v]=g[u][v];
                    p[v]=u;
                }
            }
        }
    }
    int s=0;
    rep(i,n){
        if(p[i]!=-1)s+=g[i][p[i]];
    }
    return s;
}

void run(){
    cin>>n;
    g=vvi(n,vi(n));
    rep(i,n){
        rep(j,n){
            int c;
            cin>>c;
            g[i][j]=c==-1?inf:c;
        }
    }
    cout<<prim()<<endl;
}

C++: #include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll MinimumSpanningTree(const V<V<pair<ll, int>>> &g, int n) { // 最小全域木
    using pi = pair<ll,int>; // pair = (cost, to);
    ll res = 0;

    vector<int> v;
    v.push_back(0);
    priority_queue<pi, vector<pi>, greater<pi>> pq; 
    vector<bool> seen(n);
    seen[0] = true;
    for(pi nv : g[0]) {
        pq.push(nv);
    }

    while(sz(v) != n) {
        pi p = pq.top(); pq.pop();
        if(seen[p.se]) continue;
        v.push_back(p.se);
        seen[p.se] = true;
        res += p.fi;
        for(pi nv : g[p.se]) {
            if(!seen[nv.se])
                pq.push(nv);
        }
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    V<V<pair<ll,int>>> g(n);
    rep(i,n)rep(j,n) {
        ll a;
        cin >> a;
        if(a == -1) continue;
        g[i].emplace_back(a,j);
    }
    ll ans = MinimumSpanningTree(g,n);
    cout << ans << endl;
}