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: def prim():
    distance[0] = 0
    parent[0] = -1

    while True:
        mincost = float('inf')
        for i in range(n):
            if color[i] != 'black' and distance[i] < mincost:
                mincost = distance[i]
                u = i
        if mincost == float('inf'):
            break

        color[u] = 'black'

        for v in range(n):
            if color[v] != 'black' and adjMat[u][v] != float('inf'):
                if adjMat[u][v] < distance[v]:
                    distance[v] = adjMat[u][v]
                    parent[v] = u
                    color[v] = 'gray'


n = int(input())
color = ['white'] * n
parent = [-1] * n
distance = [float('inf')] * n

adjMat = [[0] * n for _ in range(n)]
for i in range(n):
    adjRow = list(map(int, input().split()))
    for v, weight in enumerate(adjRow):
        if weight == -1:
            adjMat[i][v] = float('inf')
        else:
            adjMat[i][v] = weight

prim()

print(sum(distance))

Python: n = int(input())
adj = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    tmp = list(map(int, input().split()))
    u = tmp[0]
    u = u -1
    k = tmp[1]
    v = tmp[2:]
    for j in range(k):
        adj[u][v[j]-1] = 1
        
for i in range(n):
        print(" ".join(list(map(str, adj[i]))))

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
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):
    t = m[u][v]
    if t + 1 and d[v] > t:
      d[v] = t
print(sum(d))

Python: class Node(object):
    def __init__(self, V):
        self.V = V
        self.d = float('inf')
        self.p = -1
        self.state = -1
        # -1 -> undiscovered
        #  1 -> finished
        #  0 -> found(not finished)


M = [float('inf')] * 5
for i in range(5):
    M[i] = [float('inf')] * 5

n = int(input())
nodes = [0] * 100
for i in range(n):
    V = [int(x) for x in input().split()] 
    for (j,m) in enumerate(V):
        M[i][j] = m if not m == -1 else float('inf') 
    nodes[i] = Node([])

nodes[0].d = 0
while True:
    mincost = float('inf')
    u = -1
    for i in range(n):
        node = nodes[i]
        if (mincost > node.d) and (node.state != 1):
            u = i
            mincost = node.d

    if u == -1:
        break

    nodes[u].state = 1
    for v in range(n):
        node = nodes[v]
        if (node.state != 1) and (M[u][v] != float('inf')):
            if node.d > M[u][v]:
                node.d = M[u][v]
                node.p = u
                node.state = 0

sum = 0
for i in range(n):
    if nodes[i].p != -1:
        sum += M[i][nodes[i].p]

print(sum)

Python: def main():

    n = int(input())
    a_list = [list(map(int, input().split())) for _ in [0]*n]
    abc = []
    for i in range(n):
        for j in range(i+1, n):
            if a_list[i][j] > -1:
                abc.append((i, j, a_list[i][j]))

    def Kruskal(n, abc, weight=True):
        class unionfind():
            # size:要素数,tree：unionfind木
            def __init__(self, size):  # self,要素数
                self.size = size
                self.tree_root = list(range(self.size))
                self.tree_depth = [1]*self.size

            # rootを探す
            def root(self, index):
                temp_list = []
                temp = self.tree_root[index]
                while index != temp:
                    temp_list.append(index)
                    index = temp
                    temp = self.tree_root[index]
                for i in temp_list:
                    self.tree_root[i] = index
                return index

            # 結合
            def unite(self, index1, index2):
                r1 = self.root(index1)
                r2 = self.root(index2)
                if r1 != r2:
                    d1, d2 = self.tree_depth[r1], self.tree_depth[r2]
                    if d1 <= d2:
                        self.tree_root[r1] = r2
                        self.tree_depth[r2] = max(d1+1, d2)
                    else:
                        self.tree_root[r2] = r1
                        self.tree_depth[r1] = max(d2+1, d1)

            # 同じか判定
            def same(self, index1, index2):
                r1 = self.root(index1)
                r2 = self.root(index2)
                return r1 == r2

        uf = unionfind(n)
        ret = 0
        if weight:
            abc.sort(key=lambda x: x[2])
        for a, b, c in abc:
            if not uf.same(a, b):
                ret += c
                uf.unite(a, b)
        return ret

    print(Kruskal(n, abc))


main()

Python: n = int(input())
sides = []
ws = []
ss = []
for _ in range(n):
    sides.append(list(map(int,input().split())))
for i in range(n):
    for j in range(i+1,n):
        if sides[i][j] > 0:
            ws.append([sides[i][j],i,j])
rs = [(i) for i in range(n)]
def root(x):
    global rs
    if rs[x] == x:
        return(x)
    else:
        return(root(rs[x]))
ws.sort()
ans = 0
while(len(ws)):
    if root(ws[0][1]) != root(ws[0][2]):
        ans += ws[0][0]
        rs[root(rs[ws[0][2]])] = ws[0][1]
        ss.append(ws[0])
    del(ws[0])
print(ans)

Python: n = int(input())

A = []
# A = [[] for _ in range(n)]

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

max_d = 2001

flag = [0] * n
d = [max_d] * n
d[0] = 0
p = [-1] * n

while True:
    min_d = max_d
    for i in range(n):
        if flag[i] == 0 and d[i] < min_d:
            min_d = d[i]
            u = i
    
    if min_d == max_d:
        break
    
    flag[u] = 1
    
    for i in range(n):
        if flag[i] == 0 and A[u][i] >= 0:
            if d[i] > A[u][i]:
                d[i] = A[u][i]
                p[i] = u

print(sum(d))