Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	seen := make([]bool, n)
	for i := range list {
		list[i] = make([]int, n)
		for j := range list[i] {
			list[i][j] = scanInt()
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	sum := 0
	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if seen[node.id] {
			continue
		}
		seen[node.id] = true
		sum += node.weight

		for i, w := range list[node.id] {
			if w < 0 {
				continue
			}
			heap.Push(h, Node{id: i, weight: w})
		}
	}

	fmt.Println(sum)
}

Python: n = int(input())
#簡単のため、プリム法で回答する
data = []
for _ in range(n):
    line = list(map(int,input()[1:].split(' ')))
    for i in range(len(line)):
        if line[i] == -1:
            line[i] = 2001
    data.append(line)

been = [0]
unBeen = []
count = 0
while True:
    minIndex = [0,0]
    min = 2001
    for ele in been:
        for i in range(len(data[ele])):
            if min > data[ele][i] and not i in been:
                min = data[ele][i]
                minIndex = [ele,i]

    count += data[minIndex[0]][minIndex[1]]
    data[minIndex[0]][minIndex[1]] = 2001
    data[minIndex[1]][minIndex[0]] = 2001
    been.append(minIndex[1])
    if len(been) == n:
        break

print(count)

Python: n=int(input())
M=[list(map(int,input().split()))for _ in[0]*n]
d=[0]+[1e4]*n
b=[1]*n
a=0
while 1:
 u=-1
 for i in range(n):
  if b[i]and(u<0 or d[i]<d[u]):u=i
 if u<0:break
 b[u]=0
 a+=d[u]
 for v in range(n):
  t=M[u][v]
  if t+1 and d[v]>t:d[v]=t
print(a)

Python: n = int(input())
M = [list(map(int, input().split())) for _ in range(n)]
INF = 100000000000
color = ['White']*n
d = [INF]*n
p = [-1]*n
d[0] = 0
sum = 0

while True:
    minct = INF
    u = -1
    for i in range(n):
        if color[i] != 'Black' and d[i] < minct:
            minct = d[i]
            u = i
    if minct == INF:
        break
    color[u] = 'Black'
    for j in range(n):
        if color[j] != 'Black' and M[u][j] != -1:
            if M[u][j] < d[j]:
                d[j] = M[u][j]
                p[j] = u
                color[j] = 'Gray'
for k in range(n):
    if p[k] != -1:
        sum += M[k][p[k]]
print(sum)

Python: INF = 9999


def prim(M):
    n = len(M)
    color = [0] * n
    d = [INF] * n
    d[0] = 0

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

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
    return sum(d)


if __name__ == '__main__':
    n = int(input())
    A = []
    for i in range(n):
        src = input()
        dst = src.replace('-1', str(INF))
        ai = list(map(int, dst.split()))
        A.append(ai)
    print(prim(A))

Python: INFINITY = 10 ** 10
WHITE = 0
GRAY = 1
BLACK = 2


n = int(input())
M = [[INFINITY] * n for _ in range(n)]

for i in range(n):
    for j, weight in enumerate(map(int, input().split())):
        if weight == -1:
            weight = INFINITY

        M[i][j] = weight


def prim():
    color = [WHITE] * n
    d = [INFINITY] * n
    p = [None] * n

    d[0] = 0
    p[0] = -1

    while True:
        cost_min = INFINITY
        for i in range(n):
            if color[i] != BLACK and d[i] < cost_min:
                cost_min = d[i]
                top_now = i

        if cost_min == INFINITY:
            break
    
        color[top_now] = BLACK

        for v in range(n):
            if color[v] == BLACK or M[top_now][v] == INFINITY:
                continue

            if M[top_now][v] < d[v]:
                d[v] = M[top_now][v]
                p[v] = top_now
                color[v] = GRAY

    return sum(d)

cost_min = prim()
print(cost_min)

Python: def prim(n, M):
    color = [0 for _ in range(n)]
    d = [5000 for _ in range(n)]
    p = [-1 for _ in range(n)]

    d[0] = 0

    while True:
        mincost = 100000
        u = -1

        for i, dt in enumerate(d):
            if dt < mincost and color[i] != 1:
                mincost = dt
                u = i

        # ??´??°???????????£?????´???
        if mincost == 100000:
            break

        color[u] = 1

        for v in range(n):
            # ????????????, ?????????????¨???????????????¨??????
            if M[u][v] != 5000 and color[v] != 1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u

    all_sum = 0

    for i, p_dt in enumerate(p):
        if p_dt != -1:
            all_sum += M[i][p_dt]

    return all_sum


def main():
    n = int(input())
    M = []

    for _ in range(n):
        dt = input().split(' ')
        M.append([5000 if int(d) == -1 else int(d) for d in dt])

    print(M)

    answer = prim(n, M)

    print(answer)

if __name__ == '__main__':
    main()

Python: v = int(input())
G= [[int(i) for i in input().split()] for i in range(v)]
        
def prim(G, v):
    Vn = set([1])
    En = set([])
    V = set(range(1, v+1))
    while Vn != V:
        m = float('inf')
        for u in Vn:
            for v in V - Vn:
                if G[u - 1][v - 1] == -1:continue
                if G[u - 1][v - 1] < m:
                    m = G[u - 1][v -1]
                    k = (u,v)
        Vn.add(k[1])
        En.add(k)
    return En

print(sum(G[u - 1][v -1] for u,v in prim(G, v)))

Python: import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    n = int(input())
    a = []

    for i in range(n):
        a.append([int(j) for j in input().split()])

    checked = [False] * n
    tree = [0]
    checked[0] = True
    ans = 0

    for i in range(n - 1):
        min_w = float('inf')

        for u in tree:
            for j in range(n):
                if a[u][j] != -1 and not checked[j]:
                    if min_w > a[u][j]:
                        min_w = a[u][j]
                        min_n = j

        checked[min_n] = True
        tree.append(min_n)
        ans += min_w

    print(ans)



if __name__ == '__main__':
    solve()

Python: # Minimum Spanning Tree

INF = 10**5
N, *W = map(int, open(0).read().split())
W = tuple(zip(*[iter(INF if w < 0 else w for w in W)]*N))

S = set([0])
ans = 0
while len(S) < N:
    min_w = INF
    u = -1
    for v in S:
        for j, w in enumerate(W[v]):
            if j not in S and w < min_w:
                min_w = w
                u = j

    ans += min_w
    S.add(u)
    
print(ans)

Python: def prim(cost):
    sumcost = 0
    V = len(cost)
    mincost = [float('inf')] * V
    used = [False] * V
    mincost[0] = 0
    while True:
        v = -1
        for u in range(V):
            if not used[u] and (v == -1 or mincost[u] < mincost[u]):
                v = u
        if v == -1: break
        used[v] = True
        sumcost = sumcost + mincost[v]
        for u in range(V):
            if cost[u][v] == -1:
                continue
            mincost[u] = min(mincost[u], cost[v][u])
    return sumcost