Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

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

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	seen := make([]bool, n)
	for i := range list {
		list[i] = make([]int, n)
		for j := range list[i] {
			list[i][j] = scanInt()
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	sum := 0
	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if seen[node.id] {
			continue
		}
		seen[node.id] = true
		sum += node.weight

		for i, w := range list[node.id] {
			if w < 0 {
				continue
			}
			heap.Push(h, Node{id: i, weight: w})
		}
	}

	fmt.Println(sum)
}

Python: # https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_A
# 本よりこっちのほうがぶっちゃけわかりやすい http://www.deqnotes.net/acmicpc/prim/
# 螺旋本ではダイクストラとの違いをあまり解説していないが、違いはダイクストラのところで考えよう
# 記号は本に合わせる。
# 制約条件によりノードはたかだか100なのでオーダーを木にせずにナイーブに実装できる。本ではdを導入することにより計算量を少し削減している

INF = 10**5
# load data
N = int(input())
M = []  # 隣接行列
Color = []  # 訪問状態を記録 0:未訪問, 1:訪問経験あり, 2:訪問済み(用済み) #そうはこいつが2になっているノードはMST
D = []  # 本で言うd #こいつの役割はP299の図を追うとわかりやすい #MSTに隣接しているノードへのコストをノードのところに記録する
P = []  # 本で言うp # MSTにおける親を記録

for _ in range(N):
    Color.append(0)  # ノードはすべて未訪問
    D.append(INF)  # 無限で初期化しておく
    P.append(None)
    M.append([x if x != -1 else INF for x in map(int, input().split())])

# primのアルゴリズムを適応する
# ノード0からMSTを構築していく #まずはノード0をMSTに追加する
D[0] = 0
P[0] = None  # 親が存在しないことをNoneで示す

while True:  # MSTができるまで繰り返す ちなみにループの一周目は0をMSTに追加するところから始まる
    # MSTに隣接するノードへのpathの中で一番小さなコストを見つける、ついでにそのノード番号も
    min_cost = INF
    for i in range(N):
        if Color[i] != 2 and D[i] < min_cost:  # 訪問済みかつ最小値を更新したら
            min_cost = D[i]
            u = i  # uにはコストが一番小さい時のノードが追加される

    if min_cost == INF:
        break  # つながりがもうない

    Color[u] = 2  # つながるのに一番コストの小さい訪問済みに(MSTに追加)する

    for v in range(N):
        if Color[v] != 2 and M[u][v] != INF:  # MSTに追加されていなくてかつ、uとつながっている
            if M[u][v] < D[v]:  # 新たに追加したノードuからvに行くほうがコストが小さいならばそれをメモする
                D[v] = M[u][v]
                P[v] = u  # vの親の候補としてuを代入しておく(だいぶ無駄では？)
                Color[v] = 1  # 一度見たことあるのはgrayにしておくが、ぶっちゃけ意味はない

# これにてPに木構造が入ったのでこれをもとにコストを計算すれば良い
# ぶっちゃけこの操作は上のwhileに組み込み可能なんだけどあえてね
ans = 0
for i, p in enumerate(P[1:], start=1):
    ans += M[i][p]

print(ans)

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

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
    d[0] = 0
    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 = sum([M[i][p[i]] for i in range(n) if (p[i] != -1)])
    return _sum

print(prim())

Python: # -*- coding: utf-8 -*-

"""Minimum Spanning Tree"""

import sys
import os
import pprint

DEBUG = False

#fd = os.open('ALDS1_12_A.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

n = int(input())

# n x n matrix
M = []
for i in range(n):
    l = list(map(int, input().split()))
    M.append(l)

# Prim's Algorithm
INF = 1000000
visited = [False] * n
parent = [None] * n

# 0 is in T (Tree)
parent[0] = None

# distance between T and T-V
distance = [INF] * n
distance[0] = 0

while True:
    min_dist = INF
    candidate_index = None
    for i in range(n):
        if not visited[i] and distance[i] < min_dist:
            min_dist = distance[i]
            candidate_index = i

    if candidate_index is None:
        break

    if DEBUG:
        print('accepted i', candidate_index)
    visited[candidate_index] = True
    distance[candidate_index] = -1  # done

    for i in range(n):
        if not visited[i] and M[candidate_index][i] != -1 and distance[i] > M[candidate_index][i]:
            distance[i] = M[candidate_index][i]
            parent[i] = candidate_index


# Trees length
_sum = 0
for i in range(n):
    if parent[i] is not None:
        d = M[i][parent[i]]
        _sum += d
print(_sum)

Python: n=int(input())
matrix=[list(map(int,input().split())) for _ in range(n)]
weight=[]
for x in range(n):
    for y in range(x,n):
        if matrix[x][y]>=0: weight.append((x,y,matrix[x][y]))
weight.sort(key=lambda x:x[2])
ans=0
p=[i for i in range(n)]

def root(x):
    path_to_root=[]
    while p[x]!=x:
        path_to_root.append(x)
        x=p[x]
    for node in path_to_root:
        p[node]=x
    return x
    
def is_same_set(x,y):
    return root(x)==root(y)
    
def unite(x,y):
    p[root(x)]=root(y)
        
for x,y,w in weight:
    if not is_same_set(x,y):
        unite(x,y)
        ans+=w
print(ans)

Python: n = int(input())
edgeList = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(i):
        if a[j] != -1:
            edgeList.append([a[j], getRoot(i), getRoot(j)])
rootList = [-1 for i in range(n)]
sumLength = 0

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        

edgeList.sort(key=lambda x: x[0])
for e in edgeList:
    x = getRoot(e[1])
    y = getRoot(e[2])
    if x != y:
        sumLength += e[0]
        rootList[x] = rootList[y] = min(x, y)
print(sumLength)

Python: n = int(raw_input())
a = []

for i in range(n):
    inp = raw_input()
    if "-1" in inp:
        inp = inp.replace("-1","10000")
    a.append(list(map(int, inp.split())))

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

while len(v) < n:
    min_w   = 10000
    min_idx = 0
    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())
M=[list(map(int,input().split()))for _ in[0]*n]
d=[0]+[1e4]*n
b=[1]*n
a=0
while 1:
 u=-1
 for i in range(n):
  if b[i]and(u<0 or d[i]<d[u]):u=i
 if u<0:break
 b[u]=0
 a+=d[u]
 for v in range(n):
  t=M[u][v]
  if t+1 and d[v]>t:d[v]=t
print(a)