Go: package main

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

const (
	WHITE int = iota
	GRAY
	BLACK
)

type graph struct {
	G [][]int
	C []int
	D []int
	P []int
}

var INFTY = 1 << 32

func constructGraph() *graph {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	g := make([][]int, n)
	c := make([]int, n)
	d := make([]int, n)
	p := make([]int, n)

	for i := 0; i < n; i++ {
		sc.Scan()
		fields := strings.Fields(sc.Text())
		g[i] = toIntSlice(fields)
	}

	return &graph{g, c, d, p}
}

func (g *graph) initMst() {
	for i := 0; i < len(g.G); i++ {
		g.C[i] = WHITE
		g.D[i] = INFTY
	}
	g.D[0] = 0
	g.P[0] = -1
}

func (g *graph) primMst() int {
	g.initMst()

	var u int
	for {
		mincost := INFTY
		for i := 0; i < len(g.G); i++ {
			if g.C[i] != BLACK && g.D[i] < mincost {
				mincost = g.D[i]
				u = i
			}
		}

		if mincost == INFTY {
			break
		}

		g.C[u] = BLACK

		for i := 0; i < len(g.G); i++ {
			if g.C[i] != BLACK && g.existEdge(u, i) {
				if g.G[u][i] < g.D[i] {
					g.D[i] = g.G[u][i]
					g.P[i] = u
				}
			}
		}
	}

	totalCost := 0
	for _, cost := range g.D {
		totalCost += cost
	}
	return totalCost
}

func (g *graph) existEdge(u, v int) bool {
	return g.G[u][v] != INFTY && g.G[v][u] != INFTY
}

func toIntSlice(s []string) []int {
	a := make([]int, len(s))
	for i, v := range s {
		num, _ := strconv.Atoi(v)
		if num == -1 {
			num = INFTY
		}
		a[i] = num
	}
	return a
}

func main() {
	g := constructGraph()
	fmt.Println(g.primMst())
}

Python: from enum import Enum


class Mst(object):
    """ minimum spanning tree """
    INFINITY = 999999999
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, data):
        num_of_nodes = len(data)+1
        self.color = [Mst.Status.white] * (num_of_nodes + 1)  # ????????????????¨??????¶???
        self.M = self._make_matrix(data)  # data????????????????????£??\??????
        self.d = [Mst.INFINITY] * num_of_nodes
        self.p = [-1] * num_of_nodes

    def _make_matrix(self, data):
        graph_table = []
        for d in data:
            t = [self.inf_or_num(x) for x in d]
            graph_table.append(t)
        return graph_table

    def inf_or_num(self, n):
        if n == -1:
            return Mst.INFINITY
        else:
            return n

    def prim(self):
        self.d[0] = 0
        self.p[0] = -1

        while True:
            mincost = Mst.INFINITY
            for i in range(len(self.d)-1):
                if self.color[i] != Mst.Status.black and self.d[i] < mincost:
                    mincost = self.d[i]
                    u = i

            if mincost == Mst.INFINITY:
                break

            self.color[u] = Mst.Status.black
            for v in range(len(self.d)-1):
                if self.color[v] != Mst.Status.black and self.M[u][v] != Mst.INFINITY:
                    if self.M[u][v] < self.d[v]:
                        self.d[v] = self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Mst.Status.gray

        results = []
        for i in range(len(self.p)):
            if self.p[i] != -1:
                results.append(self.M[i][self.p[i]])
        return sum(results)



if __name__ == '__main__':
    # ??????????????\???
    n = int(input())
    data = []
    for _ in range(n):
        data.append(list(map(int, input().strip().split(' '))))

    mst = Mst(data)
    print(mst.prim())

Python: n = int(input())
primINF = 2000000000
matrix = []
numV = n
for i in range(n):
    matrix.append(list(map(int, input().split())))

visited = [False] * numV
cost = [primINF] * numV # cost
parent = [-1] * numV # parent node

cost[0] = 0
parent[0] = -1

while True:
    # 訪問済み隣接の最小コストのノードを探索する
    mincost = primINF
    for i in range(n):
        if visited[i] is False and cost[i] < mincost:
            mincost = cost[i]
            u = i
    # 見つからなければ終了する
    if mincost == primINF:
        break
    # 訪問済みにする
    visited[u] = True
    for v in range(n):
        if visited[v] is False and matrix[u][v] != -1:
            if matrix[u][v] < cost[v]:
                cost[v] = matrix[u][v]
                parent[v] = u
res = 0
for i in range(n):
    if parent[i] != -1:
        res += matrix[i][parent[i]]

print(res)

Python: n = int(input())
M = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(n):
 L = list(map(int, input().split()))
 for j,v in enumerate(L):
  if v != -1:
   M[i][j] = v

def prim():
 color = [0] * n
 d = [float("inf")] * n
 p = [-1] * n
 d[0] = 0

 while True:
  minv = float("inf")
  u = -1
  for i in range(n):
   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] != float("inf"):
    if d[v] > M[u][v]:
     d[v] = M[u][v]
     p[v] = u
 return sum(d)

print(prim())

Python:  #Treeอสิระท่ีเช่ือมต่อทกุๆVertixในGraph โดยพยายามหาค่าให้มีค่าต่ำที่สุดในการสร้าง

n = int(input()) #รับจำนวน node ทั้งหมด
a = []

for i in range(n):
    inp = input() #รับข้อมูลทั้งหมด
    if "-1" in inp:
        inp = inp.replace("-1","10000") #แทนที่ -1 ด้วย 100000
    a.append(list(map(int, inp.split()))) #splitข้อมูลเป็น int เก็บค่าข้อมูลไว้ใน list

w = 0
v = set()
v.add(0)

while len(v) < n: #วน loop ตามจำนวน n 
    min_w   = 10000 #min weight
    min_idx = 0 #min index
    i = 0
    for node in v:
        if min_w > min(a[node]):
            min_w = min(a[node])
            i = node
            min_idx = a[i].index(min_w)
    if min_idx in v:
        a[i][min_idx] = 10000
        continue
    else:
        w += min_w
        v.add(min_idx)

print(w)

Python: n = int(input())

adj = [list(map(int, input().split())) for i in range(n)]

def mst():
    T = [0]
    gross_weight = 0
    cnt = n - 1
    while cnt:
        ew = 2001
        for i in range(len(T)):
            for tv, tew in enumerate(adj[T[i]]):
                if (tv not in T) and (tew != -1):
                    if tew < ew:
                        v, ew = tv, tew
        T.append(v)
        gross_weight += ew
        cnt -= 1
    print(gross_weight)


mst()

Python: from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.child = []

n = int(input())
g = []
# mst = [[] for _ in range(n)]
# mst = [None for _ in range(n)]

for i in range(n):
    g.append(list(map(int, input().split())))

# print(g)

for i in range(n):
    for j in range(n):
        if g[i][j] == -1:
            g[i][j] = 10**5

mst = Node(0)
# done = set()

def getClosestVertex(done):
    w = 10**10
    closest = None
    for i in done:
        for j in range(len(g[i])):
            if j in done:
                continue
            if g[i][j] < w:
                w = g[i][j]
                closest = j
    return closest, w

done = set()
done.add(0)
ans = 0

while True:
    closest, w = getClosestVertex(done)
    if closest is None:
        break
    else:
        done.add(closest)
        ans += w

print(ans)

Python: from sys import stdin
INF = 1<<21
WHITE, GRAY, BLACK = 0, 1, 2
n = int(stdin.readline())
M = [[INF] * n for _ in range(n)]
for i in range(0, n):
    for j, e in enumerate(list(map(int, stdin.readline().split()))):
        if e != -1: M[i][j] = e
d = [INF] * n
d[0] = 0
color = [False] * n
def prim():
    while True:
        minv = INF
        u = -1
        for i in range(0, n):
            if minv > d[i] and color[i] != True:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = True
        for v in range(0, n):
            if color[v] != True and d[v] > M[u][v]:
                d[v] = M[u][v]
    return sum(d)
print(prim())