Go: package main

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

const (
	MAX_N      = 200
	MAX_WEIGHT = 2000
)

type Edge struct {
	start  int
	end    int
	weight int
}

type ShortestInfo struct {
	edges    []Edge
	shortest int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	shortestList := make([]ShortestInfo, n)
	for i := 1; i < n; i++ {
		shortestList[i] = ShortestInfo{edges: []Edge{}, shortest: MAX_N*MAX_WEIGHT + 1}
	}

	adjacentMatrix := make([][]int, n)
	for i := 0; i < n; i++ {
		adjacentMatrix[i] = make([]int, n)
		for j := 0; j < n; j++ {
			v, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			adjacentMatrix[i][j] = v
		}
	}

	mst([]int{1}, shortestList, adjacentMatrix)
	fmt.Println(calculateMinWeight(shortestList))
}

func calculateMinWeight(shortestList []ShortestInfo) int {
	visitedList := make([]bool, len(shortestList))
	visitedList[0] = true
	sumWeight := 0
	for !visitedAll(visitedList) {
		shortestInfo := shortestList[0]
		shortestList = shortestList[1:]
		edges := shortestInfo.edges
		for _, edge := range edges {
			if !visitedList[edge.end-1] {
				visitedList[edge.end-1] = true
				sumWeight += edge.weight
			}
		}
	}
	return sumWeight
}

func visitedAll(visitedList []bool) bool {
	for _, v := range visitedList {
		if !v {
			return false
		}
	}
	return true
}

func mst(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]int) {
	for len(nodeStack) > 0 {
		currentNode := nodeStack[0]
		nodeStack = nodeStack[1:]
		currentShortest := getShortest(currentNode, shortestList)
		adjacents := findAdjacents(currentNode, adjacentMatrix)
		for i := 0; i < len(adjacents); i++ {
			adj := adjacents[i]
			s := getShortest(adj.end, shortestList)
			if currentShortest.shortest+adj.weight < s.shortest || (currentShortest.shortest+adj.weight == s.shortest && len(currentShortest.edges)+1 > len(s.edges)) {
				setShortest(adj.end, adj, currentShortest, shortestList)
				nodeStack = append(nodeStack, adj.end)
			}
		}
	}
}

func getShortest(node int, shortestList []ShortestInfo) ShortestInfo {
	return shortestList[node-1]
}

func setShortest(node int, edge Edge, currentShortest ShortestInfo, shortestList []ShortestInfo) {
	newEdges := make([]Edge, len(currentShortest.edges)+1)
	for i := 0; i < len(newEdges)-1; i++ {
		newEdges[i] = currentShortest.edges[i]
	}
	newEdges[len(newEdges)-1] = edge
	shortestInfo := ShortestInfo{edges: newEdges, shortest: currentShortest.shortest + edge.weight}
	shortestList[node-1] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]int) []Edge {
	adjacents := adjacentMatrix[currentNode-1]
	edges := []Edge{}
	for i, v := range adjacents {
		if v > 0 {
			edges = append(edges, Edge{start: currentNode, end: i + 1, weight: v})
		}
	}
	return edges
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

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