Go: package main

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

//util
var sc = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func printList(list []int) {
	n := len(list)
	buf := bufio.NewWriter(os.Stdout)
	for _, v := range list[0 : n-1] {
		buf.Write([]byte(fmt.Sprintf("%d ", v)))
	}
	buf.Write([]byte(fmt.Sprintf("%d\n", list[n-1])))
	buf.Flush()
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

//solve
const (
	MAX   = 100
	INFTY = (1 << 21)
	WHITE = 0
	GRAY  = 1
	BLACK = 2
)

//V: グラフの頂点全体の集合
//T: MSTに属する頂点の集合
var (
	n     int
	M     [MAX][MAX]int //重みを記録する隣接行列
	color [MAX]int
	p     [MAX]int //MSTにおける頂点の親を記録
	d     [MAX]int //Tに属する頂点と、V−Tに属する頂点を繋ぐ辺の中で、重みが最小のものを記録
)

func prim() int {
	var u, minv int
	//初期化
	for i := 0; i < n; i++ {
		d[i] = INFTY
		p[i] = -1
		color[i] = WHITE
	}

	d[0] = 0

	for {
		//頂点uを決めていく
		//つまり、Tに属する頂点と、V−Tに属する頂点を繋ぐ辺の中で、重みが最小のものを決める
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			//未訪問かつ、辺の重みが最小となるuを選ぶ
			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] != INFTY {
				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() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {

		for j := 0; j < n; j++ {
			tmp := nextInt()
			if tmp == -1 {
				tmp = INFTY
			}
			M[i][j] = tmp
		}

	}

	fmt.Println(prim())

}

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