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 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]:
        heapq.heappush(queue, e)
    visited |= {one}
print(answer)

Python: def prim(n):
    d[0] = 0
    while True:
        cost_min = 10**9
        u = -1
        for i in range(n):
            weight = d[i]
            if flag_list[i] < 2 and weight < cost_min:
                u = i
                cost_min = weight
        if u == -1:
            break
        flag_list[u] = 2
        for v in range(n):
            edge = m[u][v]
            if flag_list[v] < 2 and edge > -1:
                if d[v] > edge:
                    d[v] = edge
                    p[v] = u
                    flag_list[v] = 1
    cnt = 0
    for i in range(n):
        if p[i] != -1:
            cnt += m[i][p[i]]
    return cnt


if __name__ == "__main__":
    n = int(input())
    m = []
    for _ in range(n):
        in_list = list(map(int, input().split()))
        m.append(in_list)

    flag_list = [0]*n # 0: 未到達, 1: 処理中, 2: 完了
    d = [10**9]*n
    p = [-1]*n
    print(prim(n))

Python: def kruskal(n):
    cost = []
    tree = [{i} for i in range(n)]
    while edge:
        cmin = min(weight)
        index = weight.index(cmin)
        i, j = edge[index]
        del weight[index], edge[index]
        for t in tree:
            if {i, j} <= t:
                break
        else:
            cost.append(cmin)
            for n in range(len(tree)):
                if i in tree[n]:
                    tmp = tree[n]
                    del tree[n]
                    break
            for n in range(len(tree)):
                if j in tree[n]:
                    tree[n] |= tmp
                    break
    return sum(cost)

n = int(input())
edge = []
weight = []
for i in range(n):
    for j, c in enumerate(map(int, input().split())):
        if c != -1 and not {i, j} in weight:
            edge.append({i, j})
            weight.append(c)
print(kruskal(n))

Python: 
INFINITY = 10 ** 10
WHITE = 0
GRAY = 1
BLACK = 2


n = int(input())
M = [[INFINITY] * n for _ in range(n)]

for i in range(n):
    for j, weight in enumerate(map(int, input().split())):
        if weight == -1:
            weight = INFINITY

        M[i][j] = weight


def prim():
    color = [WHITE] * n
    d = [INFINITY] * n
    p = [None] * n

    d[0] = 0
    p[0] = -1

    while True:
        cost_min = INFINITY
        for i in range(n):
            if color[i] != BLACK and d[i] < cost_min:
                cost_min = d[i]
                top_now = i

        if cost_min == INFINITY:
            break
    
        color[top_now] = BLACK

        for v in range(n):
            if color[v] == BLACK or M[top_now][v] == INFINITY:
                continue

            if M[top_now][v] < d[v]:
                d[v] = M[top_now][v]
                p[v] = top_now
                color[v] = GRAY

    return sum(d)

cost_min = prim()
print(cost_min)

Python: n=int(input())
m = [[-1 for i in range(n)] for j in range(n)]
for i in range(n): #隣接の辺のコストを入力
  nums = list(map(int, input().split()))
  for j in range(n):
    m[i][j] = nums[j]

d=[0]+[10**9]*(n-1)
visited=[0]*n

while 1:
  u=-1
  for i in range(n):
    if not visited[i] and (u<0 or d[i]<d[u]):
      u = i
  if u < 0:
    break
  visited[u]=1
  for v in range(n):
    if not visited[v] and m[u][v]!=-1:
      if m[u][v]<d[v]:
        d[v]=m[u][v]

print(sum(d))

Python: N = int(input())
G = [[] for i in range(N)]
for v in range(N):
    for w, c in enumerate(map(int, input().split())):
        if c != -1:
            G[v].append((w, c))

from heapq import heappush, heappop, heapify
used = [0]*N
que = [(c, w) for w, c in G[0]]
used[0] = 1
heapify(que)

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for w, c in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))
print(ans)

Python: n = int(input())
m = [[-1 for i in range(n)] for j in range(n)] #お隣さんへのコストを保存（この中から最小を探す）

v = set()
v.add(0)

for i in range(n): #隣接の辺のコストを入力
  nums = list(map(int, input().split()))
  for j in range(n):
    m[i][j] = nums[j]


def prim_mst(n):
  isVisited = [False] * n
  d = [0] + [2001] * (n-1)      #TとV-Tのを繋ぐ最小辺の重みを格納する

  while  True:
    mincost = 2001
    for i in range(n):
      if not (isVisited[i]) and d[i] < mincost:
        mincost = d[i]
        u = i
    isVisited[u] = True


    if mincost == 2001:        #mincostが2001になったら繰り返し作業終了
      break

    for v in range (n):
      if (not isVisited[v]) and (m[u][v] != -1):
        if m[u][v] < d[v]:
          d[v] = m[u][v]
  print(sum(d))

prim_mst(n)

Python: n = int(input())
A = [[int(i) for i in input().split(" ")] for j in range(n)]

dp1={}

for i in range(n):
    for j in range(n):
        if A[i][j] != -1 :
            dp1[(i,j)] = A[i][j]
key = []
value = []
for i,j in sorted(dp1.items(), key=lambda x:x[1]):
    key.append(i)
    value.append(j)

c_v = []
N = len(key)
len_c_v = 0
ans = 0
itr = 0
while itr != N:
    if len_c_v == n:
        break
    i = key[itr][0]
    j = key[itr][1]
    if (i in c_v) == False and (j in c_v) == False:
        c_v.append(i)
        c_v.append(j)
        ans += value[itr]
        len_c_v += 2
        itr += 1
    elif (i in c_v) == False:
        c_v.append(i)
        ans += value[itr]
        itr += 1
        len_c_v += 1
    elif (j in c_v) == False:
        c_v.append(j)
        ans += value[itr]
        itr += 1
        len_c_v += 1
    else:
        itr += 1


if len_c_v != n:
    print(-1)
else:
    print(ans)