Go: package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	matrix   []int // 隣接行列
	minToMst int   // MSTへの重み最小値
	parent   int   // 最小値の相手
	color    color
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i].matrix = eAtoi((strings.Fields(eGetline(scanner))))
		nodes[i].parent = -1
		nodes[i].minToMst = math.MaxInt16
		nodes[i].color = white
	}

	// 初回はnode[0]がMSTに入るように,minToMstを設定
	nodes[0].minToMst = 0
	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか
		min := math.MaxInt16
		u := -1
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].minToMst < min {
				u = i
				min = nodes[i].minToMst
			}
		}

		if u == -1 {
			break
		}
		// MSTに追加する頂点決定
		nodes[u].color = mst

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みを更新
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].matrix[u] == -1 {
				// 接してない
				continue
			}
			if nodes[i].matrix[u] < nodes[i].minToMst {
				// node[u]との重みが最小
				nodes[i].minToMst = nodes[i].matrix[u]
				nodes[i].parent = u
			}
		}
	}

	sum := 0
	for _, v := range nodes {
		// node[0]はparentが入っていない
		if v.parent != -1 {
			sum += v.matrix[v.parent]
		}
	}
	fmt.Println(sum)
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

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

Python: n = int(input())
A = [[int(i) for i in input().strip().split(" ")] for j in range(n)]

dp1={}

for i in range(n):
    for j in range(n):
        if A[i][j] != -1 :
            dp1[(i,j)] = A[i][j]
key = []
value = []
for i,j in sorted(dp1.items(), key=lambda x:x[1]):
    key.append(i)
    value.append(j)

c_v = []
N = len(key)
len_c_v = 0
ans = 0
itr = 0
while itr != N:
    if len_c_v == n:
        break
    i = key[itr][0]
    j = key[itr][1]
    if (i in c_v) == False and (j in c_v) == False:
        c_v.append(i)
        c_v.append(j)
        ans += value[itr]
        len_c_v += 2
        itr += 1
    elif (i in c_v) == False:
        c_v.append(i)
        ans += value[itr]
        itr += 1
        len_c_v += 1
    elif (j in c_v) == False:
        c_v.append(j)
        ans += value[itr]
        itr += 1
        len_c_v += 1
    else:
        itr += 1


if len_c_v != n:
    print(-1)
else:
    print(str(ans))

Python: def Serch():
    unit = [2001]
    for j in Tree:
        for i in range(1, n):
            G[j][i] = int(G[j][i])
            if G[j][i] != -1 and i not in Tree:
                unit.append(G[j][i])
    for j in Tree:
        for i in range(1, n):
            if G[j][i] == min(unit) and i not in Tree:
                ans.append(int(G[j][i]))
                Tree.append(i)
                Serch()
                break


n = int(input())
G = []
for i in range(n):
    G.append(input().split())

ans = []
Tree = [0]
Serch()
print(sum(ans))

Python: # input
n = int(input())
A = []
for _ in range(n):
    A.append(list(map(int, input().split())))
    
# 変数定義
inf = 100 * 2000 + 1
M = A.copy()
M = [[a if a > -1 else inf for a in line] for line in M]
d = [inf] * n
V = set([i for i in range(n)])
T = set()

# 探索
start = 0
target = start
d[target] = 0
T.add(target)
while V != T:
    for i in (V - T):
        if M[target][i] < d[i]:
            d[i] = M[target][i]

    min_wheght = min([d[i] for i in (V - T)])
    min_path = [i for i in (V - T) if d[i] == min_wheght][0]
    target = min_path
    T.add(target)

# 出力
print(sum(d))