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: # -*- coding: utf_8 -*-
level = False
def debug(v):
    if level:
        print(v)

n = int(input())
g = []

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

debug(g)

def prim(n):
    visited = [False] * n
    d = [0] + [2001] * (n - 1)
    p = [-1] * n

    while True:
        mincost = 2001

        for i in range(n):
            if (not visited[i]) and (d[i] < mincost):
                mincost = d[i]
                u = i
        if mincost == 2001:
            break
        visited[u] = True

        for v in range(n):
            if (not visited[v]) and (g[u][v] != -1):
                if g[u][v] < d[v]:
                    d[v] = g[u][v]
                    p[v] = u

    print(sum(d))

prim(n)

Python: MAX = 100
INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2
d = [INFTY for i in range(n)]
p = [-1 for i in range(n)]
color = [WHITE for i in range(n)]
d[0] = 0

n = int(input())
M = [[map(int, input().split()) for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if (M[i][j] == -1):
            M[i][j] = INFTY

def prim():
    global M, d, p, color
    while(1):
        minv = INFTY
        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] != INFTY):
                if (d[v] > M[u][v]):
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY
    
    _sum([M[i][p[i]] for i in range(n) if (p[i] != -1)])

print(prim())

Python: import queue

INFTY=1<<21

#プリム法
def prim(n,EdgeMatrix):

    EdgeList=queue.PriorityQueue() #探索対象の辺
    used=[False]*n #頂点の使用情報

    used[0]=True #0から探索を始める
    LastNode=0 #最新の頂点
    count=1 #つないだ頂点の数
    EdgeSum=0 #重みの合計

    while count<n:

        for i in range(len(EdgeMatrix[LastNode])):
            #探索していない頂点へ辺があればキューに追加
            Edge=EdgeMatrix[LastNode][i]
            if used[Edge[0]]==False:
                EdgeList.put([Edge[1],Edge[0]])

        #探索していない頂点への最も重みの小さい辺を取り出す
        while True:
            minEdge=EdgeList.get()
            if used[minEdge[1]]==False:
                break

        EdgeSum+=minEdge[0] #辺の合計を増やす
        LastNode=minEdge[1] #最新の頂点を更新
        used[minEdge[1]]=True #頂点の使用情報を更新
        count+=1 #つないだ頂点の数を更新

    return EdgeSum


#入力
n=int(input())

#辺の隣接行列
EdgeMatrix=[[] for i in range(n)]
for i in range(n):
    l=list(map(int,input().split()))
    for j in range(n):
        if l[j]!=-1:
            EdgeMatrix[i].append([j,l[j]])
            EdgeMatrix[j].append([i,l[j]])

#最小全域木の重みの総和
print(prim(n,EdgeMatrix))

Python: #minimum spaning tree

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
d = [0] + [1e4]*(n-1)
color = [0]*n

# break = 1 ; glay = 2
while 1:
    mincost = pow(10, 4)
    for i in range(n):
        if color[i] != 1 and d[i] < mincost:mincost = d[i];min_key = i
    if mincost == pow(10,4):
        break
    
    color[min_key] = 1
    
    for i in range(n):
        if color[i] != 1 and a[min_key][i] != -1 and d[i] > a[min_key][i]:
            d[i] = a[min_key][i]
            color[i] = 2
#             parent[i] = min_key
print(f"{sum(d)}")

Python: # -*- coding: utf-8 -*-
from collections import deque


class Graph:
    def __init__(self, n, adj_matrix, default_value=float('inf')):
        self.n = n
        self.adj_matrix = adj_matrix
        self.default_value = default_value

    def show(self):
        for _ in self.adj_matrix:
            print(*_)

    def set_mst(self, start=0):  # minimum spanning tree
        self.mst = []
        T = [start]

        for _ in range(self.n):
            u, (v, cost) = min(
                [(u,
                  min([(i, cost) for i, cost in enumerate(self.adj_matrix[u])
                       if cost != self.default_value],
                      key=lambda x: x[1])) for u in T],
                key=lambda x: x[1][1])
            self.mst.append((u, v))
            T.append(v)

    def show_mst(self):
        self.set_mst()
        print(sum([self.adj_matrix[u][v] for u, v in self.mst]))

    def dfs(self):
        self.states = [2] * self.n
        self.d = [None] * self.n
        self.f = [None] * self.n
        self.time = 0

        for u in range(self.n):
            if self.states[u] == 2:
                self.dfs_visit(u)

    def dfs_visit(self, u):
        self.states[u] = 1
        self.time += 1
        self.d[u] = self.time

        for v, edge in [(v, edge) for v, edge in enumerate(self.adj_matrix[u])
                        if edge]:
            if self.states[v] == 2:
                self.dfs_visit(v)

        self.states[u] = 0
        self.time += 1
        self.f[u] = self.time

    def show_dfs(self, start=0):
        self.dfs()
        for i, (d, f) in enumerate(zip(self.d, self.f)):
            print(i + 1, d, f)

    def bfs(self, start):
        self.states = [0] * self.n
        self.dists = [float('inf')] * self.n

        queue = deque([start])
        self.dists[start] = 0
        while queue:
            u = queue.popleft()
            edges = self.adj_matrix[u]

            for v, edge in [(v, edge) for v, edge in enumerate(edges) if edge]:
                if self.states[v]:
                    continue

                if self.dists[v] > self.dists[u] + 1:
                    self.dists[v] = self.dists[u] + 1
                queue.append(v)

                self.states[v] = 1

        self.dists = [
            -1 if dist == float('inf') else dist for dist in self.dists
        ]

    def show_bfs(self, start=0):
        self.bfs(start=start)
        for i, dist in enumerate(self.dists):
            print(i + 1, dist)


if __name__ == '__main__':
    n = int(input())
    adj_matrix = [[
        int(cost) if int(cost) != -1 else float('inf')
        for cost in input().split()
    ] for i in range(n)]

    g = Graph(n, adj_matrix)
    g.show_mst()

Python: import heapq

n = int(input())
A = [[int(i) for i in input().split()] for i in range(n)]
h = []
DP = {}
heapq.heappush(h,(0,0))
c = 0
while(True):
    tmp = heapq.heappop(h)
    if tmp[1] in DP:
        continue
    c += tmp[0]
    DP[tmp[1]] = 1
    if len(DP) == n:
        break
    for i,j in enumerate(A[tmp[1]]):
        if j > 0 and not i in DP:
            heapq.heappush(h,(j,i))
print(c)