Go: package main

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

const (
	white int = iota
	gray
	black
)
const INFTY int = 2001

var G [][]int
var color []int
var d []int
var p []int
var N int

func prim() int {
	u := 0
	d[u] = 0
	for {
		minCost := INFTY
		for i:=0; i<N; i++ {
			if color[i] != black && d[i] < minCost {
				minCost = d[i]
				u = i
			}
		}

		if minCost == INFTY {
			break
		}

		color[u] = black

		for v:=0; v<N; v++ {
			if color[v] != black && G[u][v] != -1 {
				if G[u][v] < d[v] {
					d[v] = G[u][v]
					p[v] = u
					color[v] = gray
				}
			}
		}
	}
	// sum
	sum := 0
	for i:=0; i<N; i++ {
		if p[i] != -1 {
			sum += G[i][p[i]]
		}
	}
	return sum
}




func initVariable(N int) {
	G = make([][]int, N)
	for i:=0; i<N; i++ {
		G[i] = make([]int, N)
	}
	color = make([]int, N)
	d = make([]int, N)
	p = make([]int, N)
	for i:=0; i<N; i++ {
		d[i] = INFTY
		p[i] = -1
	}
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	N = nextInt(scanner)
	initVariable(N)
	for i:=0; i<N; i++ {
		for j:=0; j<N; j++ {
			G[i][j] = nextInt(scanner)
		}
	}
	fmt.Printf("%d\n", prim())
}

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