Go: package main

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

const (
	MAX = 100
	INF = 1 << 21
	WHITE = 0
	GRAY = 1
	BLACK = 2
)

var (
	n int
	M [MAX][MAX]int
)

func prim() int {
	var u, minv int
	var d [MAX]int
	var p [MAX]int
	var color [MAX]int

	for i := 0; i < n; i++ {
		d[i] = INF
		p[i] = -1
		color[i] = WHITE
	}
	d[0] = 0
	for {
		minv = INF
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}
		if u == -1 {
			break
		}
		color[u] = BLACK
		for v := 0; v < n; v++ {
			if color[v] != BLACK && M[u][v] != INF {
				if d[v] > M[u][v] {
					d[v] = M[u][v]
					p[v] = u
					color[v] = GRAY
				}
			}
		}
	}
	sum := 0
	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += M[i][p[i]]
		}
	}
	return sum
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Scan()
	n, _ = strconv.Atoi(scanner.Text())
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			scanner.Scan()
			e, _ := strconv.Atoi(scanner.Text())
			if e == -1 {
				M[i][j] = INF
			} else {
				M[i][j] = e
			}
		}
	}
	fmt.Println(prim())
}

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], i, j])
rootList = [-1]*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: import heapq
from collections import defaultdict
v_num = int(input())
edges = defaultdict(list)
for i in range(v_num):
    data = [int(n) for n in input().split(" ")[1:]]
    for j in range(i + 1, v_num):
        if data[j] != -1:
            edges[i].append([data[j], j])
            edges[j].append([data[j], i])
queue = []
heapq.heapify(queue)
for c in edges[0]:
    heapq.heappush(queue, c)
visited = {0}
answer = 0
while len(visited) < v_num:
    q = heapq.heappop(queue)
    weight, one = q[0], q[1]
    if one in visited:
        continue
    answer += weight
    for e in edges[one]:
        if e[1] not in visited:
            heapq.heappush(queue, e)
    visited |= {one}
print(answer)

Python: 
def judge_reachable(graph,start,end,flag):
    flag[start]=1
    for vertex in graph[start]:
        if(flag[vertex]==1):
            continue
        if (vertex==end):
            return 1
        if(judge_reachable(graph,vertex,end,flag)):
            return 1
    return 0



graph_n=int(input())


edge_dict={}



for i in range(graph_n):
    tmp_row=list(map(int,input().split()))
    for j in range(graph_n):
        if(tmp_row[j]!=-1):
            try:
                edge_dict[tmp_row[j]].append([i,j])
            except:
                edge_dict[tmp_row[j]]=[[i,j]]


sorted_edge=sorted(edge_dict.items())


graph=[[] for i in range(graph_n)]

edge_num=0
cost=0

for edges in sorted_edge:
    for edge in edges[1]:
        flag=[0]*graph_n
        if(judge_reachable(graph,edge[0],edge[1],flag)==0):
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
            edge_num+=1
            cost+=edges[0]
            if(edge_num ==graph_n - 1):
                break    
    if(edge_num ==graph_n -1):
        break

print(cost)

Python: n = int(input())
edgeList = []


def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        
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
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: #coding:utf-8

def prim(n,G):
    dist=0
    visited=[False]*n
    cost=[1000000]*n
    pi=[0]*n
    cost[0]=0
    pi[0]=-1
    while True:
        mincost=1000000
        u=0
        for i in range(n):
            if visited[i]==False and cost[i]<mincost:
                mincost=cost[i]
                u=i
        if mincost==1000000:
            break
        visited[u]=True

        for i in range(n):
            if visited[i]==True or G[u][i]==-1:
                continue
            if G[u][i]<cost[i]:
                cost[i]=G[u][i]
                pi[i]=u
    print(sum(cost))
    
if __name__=="__main__":
    n=int(input())
    G=[]
    for i in range(n):
        G.append(list(map(int,input().split())))
    prim(n,G)

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