Go: package main

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

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	matrix   []int // 隣接行列
	minToMst int   // MSTへの重み最小値
	parent   int   // 最小値の相手
	color    color
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i].matrix = eAtoi((strings.Fields(eGetline(scanner))))
		nodes[i].parent = -1
		nodes[i].minToMst = math.MaxInt16
		nodes[i].color = white
	}

	// 初回はnode[0]がMSTに入るように,minToMstを設定
	nodes[0].minToMst = 0
	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか
		min := math.MaxInt16
		u := -1
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].minToMst < min {
				u = i
				min = nodes[i].minToMst
			}
		}

		if u == -1 {
			break
		}
		// MSTに追加する頂点決定
		nodes[u].color = mst

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みを更新
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].matrix[u] == -1 {
				// 接してない
				continue
			}
			if nodes[i].matrix[u] < nodes[i].minToMst {
				// node[u]との重みが最小
				nodes[i].minToMst = nodes[i].matrix[u]
				nodes[i].parent = u
			}
		}
	}

	sum := 0
	for _, v := range nodes {
		// node[0]はparentが入っていない
		if v.parent != -1 {
			sum += v.matrix[v.parent]
		}
	}
	fmt.Println(sum)
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

Python: import sys

if __name__ == "__main__":
    # lines = """5
    # -1 2 3 1 -1
    # 2 -1 -1 4 -1
    # 3 -1 -1 1 1
    # 1 4 1 -1 3
    # -1 -1 1 3 -1
    # """.split("\n")
    lines = sys.stdin.readlines()
    matrix = [[int(x) for x in line.strip().split(" ")] for line in lines[1:] if line.strip() != ""]

    connections = set([0])  # ??\?¶????????????????
    dimension = int(lines[0])
    cost = 0

    while len(connections) < dimension:
        minimum = sys.maxsize
        candidate = None

        for i in connections:
            for index, value in enumerate(matrix[i]):
                if value != -1 and value < minimum and index not in connections:
                    minimum = matrix[i][index]  # minimum = value
                    candidate = index

        connections.add(candidate)
        cost += minimum

    # print(connections, cost)
    print(cost)

Python: from heapq import heappush, heappop, heapify

n = int(input())
G = [[] for _ in range(n)]

for i in range(n):
    for j,dist in enumerate(map(int,input().split())):
        if dist != -1:
            G[i].append((j,dist))
sum = 0

def prim(n):
    que = [(w,c) for c,w in G[0]]
    heapify(que)
    color = [0]*n
    color[0] = 1
    global sum
    while que:
        w,node = heappop(que)
        if color[node] == 1:
            continue
        color[node] = 1
        sum += w
        for x,y in G[node]:
            if color[x] == 1:
                continue
            heappush(que,(y,x))
    return sum

print(prim(n))

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)