Go: package main

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

const R = 100000000

var sc = bufio.NewScanner(os.Stdin)

var n int
var A [101][101]int

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func prim() int {
	var u, Minimum, sum int
	var d, p, color [101]int

	for i := 0; i < n; i++ {
		d[i] = R
		p[i] = -1
		color[i] = 0
	}
	d[0] = 0

	for {
		Minimum = R
		u = -1
		for i := 0; i < n; i++ {
			if Minimum > d[i] && color[i] != 2 {
				u = i
				Minimum = d[i]
			}
		}
		if u == -1 {
			break
		}
		color[u] = 2
		for j := 0; j < n; j++ {
			if color[j] != 2 && A[u][j] != R {
				if d[j] > A[u][j] {
					d[j] = A[u][j]
					p[j] = u
					color[j] = 1
				}
			}
		}
	}

	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += A[i][p[i]]
		}
	}
	return sum
}
func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			e := nextInt()
			if e == -1 {
				A[i][j] = R
			} else {
				A[i][j] = e
			}
		}
	}
	fmt.Println(prim())
}

Python: import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

    def same(self, x, y):
        return self.root(self.tree[x]) == self.root(self.tree[y])

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.tree[x] = y


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    uf = UnionFind(N)
    ret = 0
    cost = []
    for i in range(N):
        D = il()
        for j in range(N):
            if D[j] != -1:
                cost.append((D[j], i, j))
    else:
        cost.sort()
        for c, v1, v2 in cost:
            if not uf.same(v1, v2):
                ret += c
                uf.unite(v1, v2)
        print(ret)


if __name__ == '__main__':
    main()

Python: import sys

inf = float('inf')

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 prim(n, As):
    checked = [False] * n
    d = [inf] * n
    checked[0] = True
    d[0] = 0
    nxt = 0
    tot_wgt = 0

    for i in range(n - 1):
        for j in range(n):
            if As[nxt][j] < d[j]:
                d[j] = As[nxt][j]

        min_w = inf
        min_n = 0
        for j in range(n):
            if not checked[j] and min_w > d[j]:
                min_w = d[j]
                min_n = j

        tot_wgt += min_w
        nxt = min_n
        checked[nxt] = True

    return tot_wgt

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

    for i in range(n):
        line = [int(j) for j in input().split()]
        As.append([i if i != -1 else inf for i in line])

    ans = prim(n, As)

    print(ans)


if __name__ == '__main__':
    solve()

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: #coding: utf-8

inf = 1000000000
n = int(input())
mtrx = []
for i in range(n):
    col2 = list(map(int,input().split()))
    col = []
    for num in col2:
        if num == -1:
            num = inf
        col.append(num)
    mtrx.append(col)

def prim():
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    p = [None for i in range(n)]
    p[0] = -1
    d[0] = 0

    while True:
        mincost = inf
        for i in range(n):
            if color[i] != "black" and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == inf:
            break

        color[u] = "black"

        for v in range(n):
            if color[v] != "black" and mtrx[u][v] != inf:
                if mtrx[u][v] < d[v]:
                    d[v] = mtrx[u][v]
                    p[v] = u
                    color[v] = "gray"
    print(sum(d))

prim()

Python: 
def prim():
    global n, color, M, d, p
    d[0] = 0

    while True:
        min_cost = 10000000000
        u = -1

        # まず始点を決める。
        for i in range(n):
            if color[i] != 'BLACK' and d[i] < min_cost:
                min_cost = d[i]
                u = i  # エッジが繋がる中で、最小のもの？？

        if u == -1:
            break

        color[u] = 'BLACK'

        for v in range(n):
            if color[v] != 'BLACK' and M[u][v] != -1:
                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


n = int(input())

color = ['WHITE'] * n
M = []
d = [10000000000] * n  # 重みが最小の辺の重み
p = [-1] * n  # MSTにおけるp[v]の親（どこから来たか？？）

for i in range(n):
    _ = list(map(int, input().split()))
    M.append(_)
# print(A)

print(prim())

Python: #0オリジンで行うので注意
import sys
input = sys.stdin.buffer.readline

INF = 10 ** 9


#隣接行列
n = int(input())
G = []
for _ in range(n):
    G.append(list(map(int, input().split())))
for i in range(n):
    for j in range(n):
        if G[i][j] == -1:
            G[i][j] = INF

#到着してない：white,　到着後:gray, 確定:black
white, gray, black = 1, 2, 3
color = [white] * n #初期条件

d = [INF] * n #d[m]にTに属する頂点とT-Vに属する頂点を繋ぐ辺の中で重みが最小の物を記録
p = [INF] * n #p[m]にMSTにおける頂点mの親を記録


def prim():
    d[0] = 0
    p[0] = -1
    
    while True:
        mincost = INF
        for i in range(n):
            if color[i] != black and d[i] < mincost:
                mincost = d[i]
                u = i #次に伸ばす頂点の候補として記録
                
                
        if mincost == INF: #次の頂点がなかったらbreak
            break
                
        color[u] = black #最小全域木の頂点として決定
            
        for v in range(n):
            if color[v] != black and G[u][v] != INF:
                if G[u][v] < d[v]:
                    d[v] = G[u][v] #d[n]を更新を更新する
                    p[v] = u #uをvの親候補として記録
                    color[v] = gray
    
    S = 0#合計
    for i in range(n):
        if p[i] != -1:
            S += G[i][p[i]]
    return S

print(prim())

Python: MAX = 2001


def prim(tree: [int], adjacent_list: [[int]]):
    cost = 0
    next = 0
    for l in adjacent_list:
        l[next] = MAX
    while True:
        tree.append(next)
        min_list = list()
        for t in tree:
            min_list.append(min([(v, i) for i, v in enumerate(adjacent_list[t])]))
        min_cost, i = min(min_list)
        if min_cost == MAX:
            return cost
        cost += min_cost
        for l in adjacent_list:
            l[i] = MAX
        print(adjacent_list)
        next = i


if __name__ == '__main__':
    N = int(input())
    adjacent_list = [[int(e) if int(e) != -1 else MAX for e in input().rstrip().split()] for _ in range(N)]
    test_list = []
    print(prim(test_list, adjacent_list))
    print(test_list)