Go: package main

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

const (
	MAX_N      = 200
	MAX_WEIGHT = 2000
)

type Edge struct {
	start  int
	end    int
	weight int
}

type ShortestInfo struct {
	edges    []Edge
	shortest int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	shortestList := make([]ShortestInfo, n)
	for i := 1; i < n; i++ {
		shortestList[i] = ShortestInfo{edges: []Edge{}, shortest: MAX_N*MAX_WEIGHT + 1}
	}

	adjacentMatrix := make([][]int, n)
	for i := 0; i < n; i++ {
		adjacentMatrix[i] = make([]int, n)
		for j := 0; j < n; j++ {
			v, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			adjacentMatrix[i][j] = v
		}
	}

	mst([]int{1}, shortestList, adjacentMatrix)
	fmt.Println(shortestList)
	fmt.Println(calculateMinWeight(shortestList))
}

func calculateMinWeight(shortestList []ShortestInfo) int {
	visitedList := make([]bool, len(shortestList))
	visitedList[0] = true
	sumWeight := 0
	for !visitedAll(visitedList) {
		shortestInfo := shortestList[0]
		shortestList = shortestList[1:]
		edges := shortestInfo.edges
		for _, edge := range edges {
			if !visitedList[edge.end-1] {
				visitedList[edge.end-1] = true
				sumWeight += edge.weight
			}
		}
	}
	return sumWeight
}

func visitedAll(visitedList []bool) bool {
	for _, v := range visitedList {
		if !v {
			return false
		}
	}
	return true
}

func mst(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]int) {
	for len(nodeStack) > 0 {
		currentNode := nodeStack[0]
		nodeStack = nodeStack[1:]
		currentShortest := getShortest(currentNode, shortestList)
		adjacents := findAdjacents(currentNode, adjacentMatrix)
		for i := 0; i < len(adjacents); i++ {
			adj := adjacents[i]
			s := getShortest(adj.end, shortestList)
			if currentShortest.shortest+adj.weight < s.shortest || (currentShortest.shortest+adj.weight == s.shortest && len(currentShortest.edges)+1 > len(s.edges)) {
				setShortest(adj.end, adj, currentShortest, shortestList)
				nodeStack = append(nodeStack, adj.end)
			}
		}
	}
}

func getShortest(node int, shortestList []ShortestInfo) ShortestInfo {
	return shortestList[node-1]
}

func setShortest(node int, edge Edge, currentShortest ShortestInfo, shortestList []ShortestInfo) {
	newEdges := make([]Edge, len(currentShortest.edges)+1)
	for i := 0; i < len(newEdges)-1; i++ {
		newEdges[i] = currentShortest.edges[i]
	}
	newEdges[len(newEdges)-1] = edge
	shortestInfo := ShortestInfo{edges: newEdges, shortest: currentShortest.shortest + edge.weight}
	shortestList[node-1] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]int) []Edge {
	adjacents := adjacentMatrix[currentNode-1]
	edges := []Edge{}
	for i, v := range adjacents {
		if v > 0 {
			edges = append(edges, Edge{start: currentNode, end: i + 1, weight: v})
		}
	}
	return edges
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

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

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

        if mincost == float("inf"):
            break

        visited[u] = 2

        for v in range(n):
            if visited[v] != 2 and M[u][v] != float("inf"):
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
                    p[v] = u
                    visited[v] = 1
                
    ans = 0
    for i,j in enumerate(p[1:], start=1):
        ans += M[i][j]
        
    return ans


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

for _ in range(n):
    M.append([x if x != -1 else float("inf") for x in map(int, input().split())])


print(prim())

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())