Go: package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	I int
	J int
	A int
}

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]int, n)
	edges := make([]Edge, 0, n*(n-1)/2)
	parents := make([]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&g[i][j])
			if g[i][j] > 0 {
				edges = append(edges, Edge{i, j, g[i][j]})
			}
		}
		parents[i] = i
	}
	sort.SliceStable(edges, func(i, j int) bool { return edges[i].A > edges[j].A })

	sum := 0
	for len(edges) > 0 {
		edge := edges[len(edges)-1]
		edges = edges[:len(edges)-1]

		if same(edge.I, edge.J, &parents) {
			continue
		}
		union(edge.I, edge.J, &parents)
		sum += edge.A
	}
	fmt.Println(sum)
}



func root(id int, parents *[]int) int {
	if id == (*parents)[id] {
		return id
	}
	return root((*parents)[id], parents)
}

func union(i, j int, parents *[]int) {
	(*parents)[root(j, parents)] = (*parents)[root(i, parents)]
}

func same(i, j int, parents *[]int) bool {
	return root(i, parents) == root(j, parents)
}

Python: def main():

    n = int(input())
    a_list = [list(map(int, input().split())) for _ in [0]*n]
    abc = []
    for i in range(n):
        for j in range(i+1, n):
            if a_list[i][j] > -1:
                abc.append((i, j, a_list[i][j]))

    def Kruskal(n, abc, weight=True):
        class unionfind():
            # size:要素数,tree：unionfind木
            def __init__(self, size):  # self,要素数
                self.size = size
                self.tree_root = list(range(self.size))
                self.tree_depth = [1]*self.size

            # rootを探す
            def root(self, index):
                temp_list = []
                temp = self.tree_root[index]
                while index != temp:
                    temp_list.append(index)
                    index = temp
                    temp = self.tree_root[index]
                for i in temp_list:
                    self.tree_root[i] = index
                return index

            # 結合
            def unite(self, index1, index2):
                r1 = self.root(index1)
                r2 = self.root(index2)
                if r1 != r2:
                    d1, d2 = self.tree_depth[r1], self.tree_depth[r2]
                    if d1 <= d2:
                        self.tree_root[r1] = r2
                        self.tree_depth[r2] = max(d1+1, d2)
                    else:
                        self.tree_root[r2] = r1
                        self.tree_depth[r1] = max(d2+1, d1)

            # 同じか判定
            def same(self, index1, index2):
                r1 = self.root(index1)
                r2 = self.root(index2)
                return r1 == r2

        uf = unionfind(n)
        ret = 0
        if weight:
            abc.sort(key=lambda x: x[2])
        for a, b, c in abc:
            if not uf.same(a, b):
                ret += c
                uf.unite(a, b)
        return ret

    print(Kruskal(n, abc))


main()

Python: n = int(input())
sides = []
ws = []
ss = []
for _ in range(n):
    sides.append(list(map(int,input().split())))
for i in range(n):
    for j in range(i+1,n):
        if sides[i][j] > 0:
            ws.append([sides[i][j],i,j])
rs = [(i) for i in range(n)]
def root(x):
    global rs
    if rs[x] == x:
        return(x)
    else:
        return(root(rs[x]))
ws.sort()
ans = 0
while(len(ws)):
    if root(ws[0][1]) != root(ws[0][2]):
        ans += ws[0][0]
        rs[root(rs[ws[0][2]])] = ws[0][1]
        ss.append(ws[0])
    del(ws[0])
print(ans)

Python: n = int(input())

A = []
# A = [[] for _ in range(n)]

for i in range(n):
    A.append(list(map(int, input().split())))
    # A[i] = list(map(int, input().split()))

max_d = 2001

flag = [0] * n
d = [max_d] * n
d[0] = 0
p = [-1] * n

while True:
    min_d = max_d
    for i in range(n):
        if flag[i] == 0 and d[i] < min_d:
            min_d = d[i]
            u = i
    
    if min_d == max_d:
        break
    
    flag[u] = 1
    
    for i in range(n):
        if flag[i] == 0 and A[u][i] >= 0:
            if d[i] > A[u][i]:
                d[i] = A[u][i]
                p[i] = u

print(sum(d))

Python: INF = float('inf')
N = int(input())
M = []
D = []
P = []
visited = []
for i in range(N):
    M.append([a if a != -1 else INF for a in map(int, input().split())])
    D.append(INF)
    P.append(-1)
    visited.append(False)

D[0] = 0
P[0] = None

while True:
    min_cost = INF
    u = -1
    for i in range(N):
        if not visited[i] and D[i] < min_cost:
            u = i
            min_cost = D[i]

    if u == -1:
        break

    visited[u] = True

    for i, m in enumerate(M[u]):
        if not visited[i] and m != INF and m < D[i]:
            D[i] = m
            P[i] = u

print(sum(D))

Python: n = int(input())
a = []
lrg = 2000000
for i in range(n):
    tmp = list(map(int, input().split( )))
    for j in range(n):
        if tmp[j] == -1:
            tmp[j] = lrg
    a.append(tmp)
#for i in range(n):
#    print(*a[i])
V = [0]
T = []
weight = 0

while len(V)<n:
    mn = lrg-1###forの外
    tmp = -1###forの外
    for v in V:
        for i in range(n):
            if i not in V and mn>a[v][i]:
                mn = a[v][i]
                tmp = i
    weight += mn
    #print(v,[v,tmp])
    V.append(tmp)
    #print(*V)

print(weight)

Python: n = int(input())
a = []
b = []
c = []

def root(x):
    global rs
    if rs[x] == x:
        return(x)
    else:
        return(root(rs[x]))

for _ in range(n):
    a.append(list(map(int,input().split())))
for i in range(n):
    for j in range(i+1,n):
        if a[i][j] >= 0:
            b.append([a[i][j],i,j])
rs = [(i) for i in range(n)]

b.sort()
ans = 0
while(len(b)):
    if root(b[0][1]) != root(b[0][2]):
        ans += b[0][0]
        rs[root(rs[b[0][2]])] = root(b[0][1])
        c.append(b[0])
    del(b[0])
print(ans)

Python: WHITE = 0
GRAY = 1
BLACK = 2

INF = 1.0e+6

def prim(M):
    n = len(M)
    color = [WHITE] * n
    d = [INF] * n
    p = [-1] * n

    d[0] = 0

    while True:
        minv = INF
        u = -1
        for i in range(n):
            if minv > d[i] and color[i] != BLACK:
                u = i
                minv = d[i]

        if u == -1:
            break

        color[u] = BLACK
        for v in range(n):
            if color[v] != BLACK and M[u][v] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY

    sum = 0
    for i in range(n):
        if p[i] != -1:
            sum += M[i][p[i]]

    return sum


if __name__ == "__main__":
    n = int(input())

    M = [] * n

    for i in range(n):
        M.append(list(map(int, input().split())))
        M[i] = [INF if j == -1 else j for j in M[i]]

    print(prim(M))

Python: n = int(input())

INF = 2147483647
G = [[INF for j in range(n)] for i in range(n+1)]
check = [0 for i in range(n)]


def prim():
    d = [INF for i in range(n)]
    p = [-1 for i in range(n)]
    d[0] = 0
    cost = 0

    while True:
        min_cost = INF
        for i in range(n):
            if check[i] != 2 and d[i] < min_cost:
                min_cost = d[i]
                u = i

        if min_cost == INF:
            break

        cost += d[u]
        check[u] = 2

        for v in range(n):
            if check[v] != 2 and G[u][v] != INF:
                if G[u][v] < d[v]:
                    d[v] = G[u][v]
                    p[v] = u
                    check[v] = 1

    return cost


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(n):
            if data[j] != -1:
                G[i][j] = data[j]

    print(prim())


if __name__ == '__main__':
    main()