Go: package main

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

const (
	MAX = 100
	INF = 1 << 21
	WHITE = 0
	GRAY = 1
	BLACK = 2
)

var (
	n int
	M [MAX][MAX]int
)

func prim() int {
	var u, minv int
	var d [MAX]int
	var p [MAX]int
	var color [MAX]int

	for i := 0; i < n; i++ {
		d[i] = INF
		p[i] = -1
		color[i] = WHITE
	}
	d[0] = 0
	for {
		minv = INF
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}
		if u == -1 {
			break
		}
		color[u] = BLACK
		for v := 0; v < n; v++ {
			if color[v] != BLACK && 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 := 0; i < n; i++ {
		if p[i] != -1 {
			sum += M[i][p[i]]
		}
	}
	return sum
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Scan()
	n, _ = strconv.Atoi(scanner.Text())
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			scanner.Scan()
			e, _ := strconv.Atoi(scanner.Text())
			if e == -1 {
				M[i][j] = INF
			} else {
				M[i][j] = e
			}
		}
	}
	fmt.Println(prim())
}

Python: class Node(object):
    def __init__(self, V):
        self.V = V
        self.d = float('inf')
        self.p = -1
        self.state = -1
        # -1 -> undiscovered
        #  1 -> finished
        #  0 -> found(not finished)


M = [float('inf')] * 5
for i in range(5):
    M[i] = [float('inf')] * 5

n = int(input())
nodes = [0] * 100
for i in range(n):
    V = [int(x) for x in input().split()] 
    for (j,m) in enumerate(V):
        M[i][j] = m if not m == -1 else float('inf') 
    nodes[i] = Node([])

nodes[0].d = 0
while True:
    mincost = float('inf')
    u = -1
    for i in range(n):
        node = nodes[i]
        if (mincost > node.d) and (node.state != 1):
            u = i
            mincost = node.d

    if u == -1:
        break

    nodes[u].state = 1
    for v in range(n):
        node = nodes[v]
        if (node.state != 1) and (M[u][v] != float('inf')):
            if node.d > M[u][v]:
                node.d = M[u][v]
                node.p = u
                node.state = 0

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

print(sum)

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))