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 <bits/stdc++.h>
using namespace std;

typedef int64_t i64;
typedef uint64_t ui64;

class djset{
private:
    int sz;
    int *par;
public:
    djset(int n){
        sz=n;
        par=new int[sz];
        for(int i=0;i<sz;i++) par[i]=1;
    }
    int find(int x){
        return par[x]<=0?-(par[x]=-find(-par[x])):x;
    }
    void unite(int x,int y){
        int px=find(x),py=find(y);
        if(px==py) return;
        if(par[px]<par[py]){
            int tmp=px;
            px=py;
            py=tmp;
        }
        par[px]+=par[py];
        par[py]=-px;
    }
    bool same(int x,int y){
        return (find(x)==find(y));
    }
    int size(int x){
        return par[find(x)];
    }
    int group(void){
        int cnt=0;
        for(int i=0;i<sz;i++){
            if(par[i]>0) cnt++;
        }
        return cnt;
    }
    void refr(void){
        delete[] par;
    }
};

class graph{
private:
    struct vrtx{
        int to;
        int64_t cost;
    };
    struct adj{
        int start;
        int to;
        int64_t cost;
    };
    int nd;
    int edg;
public:
    std::vector<vrtx> *node;
    std::vector<adj> edge;
    graph(int n,int m){
        nd=n;
        edg=m;
        node=new std::vector<vrtx>[nd];
    }
    void add_dir(int s,int t,int64_t c){
        node[s].push_back({t,c});
        edge.push_back({s,t,c});
    }
    void add_undir(int s,int t,int64_t c){
        node[s].push_back({t,c});
        node[t].push_back({s,c});
        edge.push_back({s,t,c});
    }
    void dlt_dir(int s,int t){
        for(int i=0;i<node[s].size();i++){
            if(node[s][i].to==t){
                node[s].erase(node[s].begin()+i);
                break;
            }
        }
    }
    void dlt_undir(int s,int t){
        for(int i=0;i<node[s].size();i++){
            if(node[s][i].to==t){
                node[s].erase(node[s].begin()+i);
                break;
            }
        }
        for(int i=0;i<node[t].size();i++){
            if(node[t][i].to==s){
                node[t].erase(node[t].begin()+i);
                break;
            }
        }
    }
    void refr(void){
        for(int i=0;i<nd;i++) std::vector<vrtx>().swap(node[i]);
        delete[] node;
        std::vector<adj>().swap(edge);
    }
    bool islnk(void);
    void dfs(int r,int64_t **p,bool **vst);  // 木, (*p)[], vst[] を呼び出す前に初期化
    bool ispls(void);
    void bellford(int s,int64_t **d);
    void dijkstra(int s,int64_t **d);  // 負の閉路なし
    void bfs(int s,int64_t **d);  // 辺に重み無し or 木
    void waflo(bool isdir,int64_t ***d);
    int64_t minstw_dir(int r);  // class: djset, class: skewheap が必要
    int64_t minstw_undir(void);  // class: djset が必要
    void edmonds(int r,std::vector<std::pair<int,int>> &p);  // class: djset, class: skewheap が必要
    void kruscal(std::vector<std::pair<int,int>> &p);  // class: djset が必要
    void prim(std::vector<std::pair<int,int>> &p);
    void cumulsum(int s,int64_t **d);  // 木
    void cumulprd(int s,int64_t **d);  // 木
};

void graph::kruscal(std::vector<std::pair<int,int>> &p){
    adj *es=new adj[edg];
    for(int i=0;i<edg;i++) es[i]={edge[i].start,edge[i].to,edge[i].cost};
    std::sort(es,es+edg,[](const adj &e1,const adj &e2){return e1.cost<e2.cost;});
    djset uf(nd);
    for(int i=0;i<edg;i++){
        if(!uf.same(es[i].start,es[i].to)){
            uf.unite(es[i].start,es[i].to);
            p.push_back({es[i].start,es[i].to});
        }
    }
}

int64_t graph::minstw_undir(void){
    adj *es=new adj[edg];
    for(int i=0;i<edg;i++) es[i]={edge[i].start,edge[i].to,edge[i].cost};
    std::sort(es,es+edg,[](const adj &e1,const adj &e2){return e1.cost<e2.cost;});
    djset uf(nd);
    int64_t res=0;
    for(int i=0;i<edg;i++){
        if(!uf.same(es[i].start,es[i].to)){
            uf.unite(es[i].start,es[i].to);
            res+=es[i].cost;
        }
    }
    return res;
}

int main(void){
    int n;
    scanf("%i",&n);
    int m=0;
    i64 **d=new i64*[n];
    for(int i=0;i<n;i++){
        d[i]=new i64[n];
        for(int j=0;j<n;j++){
            scanf("%lli",&d[i][j]);
            if(d[i][j]!=-1) m++;
        }
    }
    graph g(n,m);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(d[i][j]!=-1) g.add_dir(i,j,d[i][j]);
        }
    }
    printf("%lli\n",g.minstw_undir());
    return 0;
}

C++: 

#include<iostream>
#include<vector>
#include<cinttypes>
#include<algorithm>
#include<numeric>
#include<iterator>
#include<tuple>
#include<functional>
#include<set>

using si32 = std::int32_t;
using ui32 = std::uint32_t;


int main() {

	si32 n;
	std::cin >> n;

	std::vector<std::vector<si32>> graph( n ), cost( n, std::vector<si32>( n, -1 ) );

	for( si32 i{}; i < n; ++i )
	{
		for( si32 j{}; j < n; ++j )
		{
			si32 t; std::cin >> t;

			if( t < 0 || i == j )
				continue;

			graph[i].emplace_back( j );
			graph[j].emplace_back( i );

			cost[i][j] = cost[j][i] = t;
		}
	}


	//	std::queue<>

		//edges
	std::vector<std::pair<si32, si32>> mst;
	mst.reserve( n - 1 );

	for( const auto&e : graph.front() )
		if( mst.empty() )
			mst.emplace_back( 0, e );
		else
			if( cost[0][e] < cost[ mst[0].first ][ mst[0].second ] )
				mst[0] = std::make_pair( 0, e );

	//std::cout << mst[0].first << " " << mst[0].second << "\n";


	std::set<si32> mst_vertices;
	for( const auto&v : { mst[0].first, mst[0].second } )
		mst_vertices.emplace( v );


	while( mst.size() < static_cast<decltype(mst.size())>(n - 1) )
	{
		
		si32 cost_t = 20000;
		std::pair<si32, si32> edge{ 0,0 };
		
		for( const auto& mv : mst_vertices )
		{
			for( const auto& gv : graph[mv] )
				if( mst_vertices.find( gv ) == mst_vertices.end() )
					if( cost[mv][gv] < cost_t )
					{
						edge = std::make_pair( mv, gv );
						cost_t = cost[mv][gv];
					}
		}

		mst_vertices.emplace( edge.second );
		mst.emplace_back( edge );
		/*
		std::cout << edge.first << " " << edge.second << "\n";
		std::cout<<"---\n"
			<< mst.size() << ":\n";
		for( const auto&e : mst )
			std::cout << e.first << " " << e.second << "\n";
		std::cout << "------\n";
		*/
		
	}
	
	ui32 ans{};
	for( const auto& e : mst )
	{
		ans += cost[e.first][e.second];
//		std::cout << e.first << " " << e.second << " " << cost[e.first][e.second] << " " << ans << "\n";
	}

	std::cout << ans << "\n";

	return 0;
}