Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	g := make([][]int, n)
	ans := make([][]int, n)

	inf := 1 << 30
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		ans[i] = make([]int, n)
		for ii := 0; ii < n; ii++ {
			g[i][ii] = getNextInt(scanner)
			if g[i][ii] == -1 {
				g[i][ii] = inf
			}
			ans[i][ii] = -1
		}
	}

	im := make(IntMap, 1)

	im.increment(1)

	for len(im) < n {
		min := inf
		u := -1
		v := -1
		for i := range im {
			for ii := 0; ii < n; ii++ {
				if im.get(ii) != 0 {
					continue
				}
				if min > g[i][ii] {
					min = g[i][ii]
					u = i
					v = ii
				}
			}
		}
		im.increment(v)
		ans[u][v] = min
		ans[v][u] = min
	}

	sum := 0
	for i := 0; i < n-1; i++ {
		for ii := i + 1; ii < n; ii++ {
			if ans[i][ii] != -1 {
				sum += ans[i][ii]
			}
		}
	}

	fmt.Fprintln(writer, sum)
	writer.Flush()
}

// IntMap ...
type IntMap map[int]int

func (m IntMap) get(key int) int {
	if _, ok := m[key]; ok {
		return m[key]
	}
	return 0
}
func (m IntMap) increment(key int) {
	if _, ok := m[key]; ok == false {
		m[key] = 0
	}
	m[key]++
}

Python: WHITE = 0
GRAY = 1
BLACK = 2

INF = 1.0e+6

def prim(M):
    n = len(M)
    color = [WHITE] * n
    d = [INF] * n
    p = [-1] * n

    d[0] = 0

    while True:
        minv = INF
        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] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY

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

    return sum


if __name__ == "__main__":
    n = int(input())

    M = [] * n

    for i in range(n):
        M.append(list(map(int, input().split())))
        M[i] = [INF if j == -1 else j for j in M[i]]

    print(prim(M))

Python: n = int(input())

INF = 2147483647
G = [[INF for j in range(n)] for i in range(n+1)]
check = [0 for i in range(n)]


def prim():
    d = [INF for i in range(n)]
    p = [-1 for i in range(n)]
    d[0] = 0
    cost = 0

    while True:
        min_cost = INF
        for i in range(n):
            if check[i] != 2 and d[i] < min_cost:
                min_cost = d[i]
                u = i

        if min_cost == INF:
            break

        cost += d[u]
        check[u] = 2

        for v in range(n):
            if check[v] != 2 and G[u][v] != INF:
                if G[u][v] < d[v]:
                    d[v] = G[u][v]
                    p[v] = u
                    check[v] = 1

    return cost


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(n):
            if data[j] != -1:
                G[i][j] = data[j]

    print(prim())


if __name__ == '__main__':
    main()

Python: n = int(input())
A = [[int(i) for i in input().strip().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(str(ans))

Python: def Serch():
    unit = [2001]
    for j in Tree:
        for i in range(1, n):
            G[j][i] = int(G[j][i])
            if G[j][i] != -1 and i not in Tree:
                unit.append(G[j][i])
    for j in Tree:
        for i in range(1, n):
            if G[j][i] == min(unit) and i not in Tree:
                ans.append(int(G[j][i]))
                Tree.append(i)
                Serch()
                break


n = int(input())
G = []
for i in range(n):
    G.append(input().split())

ans = []
Tree = [0]
Serch()
print(sum(ans))

Python: # input
n = int(input())
A = []
for _ in range(n):
    A.append(list(map(int, input().split())))
    
# 変数定義
inf = 100 * 2000 + 1
M = A.copy()
M = [[a if a > -1 else inf for a in line] for line in M]
d = [inf] * n
V = set([i for i in range(n)])
T = set()

# 探索
start = 0
target = start
d[target] = 0
T.add(target)
while V != T:
    for i in (V - T):
        if M[target][i] < d[i]:
            d[i] = M[target][i]

    min_wheght = min([d[i] for i in (V - T)])
    min_path = [i for i in (V - T) if d[i] == min_wheght][0]
    target = min_path
    T.add(target)

# 出力
print(sum(d))

Python: n = int(input())
A = []
for ni in range(n):
    tmp = [int(i) for i in input().split()]
    A.append([[i, t] for i, t in enumerate(tmp) if t != -1])

INF = 2001
V = [i for i in range(n)]
T = [0]
ans = 0
while len(T) != n:
    w = [-1, INF]
    for t in T:
        for a in A[t]:
            if a[1] < w[1]:
                w = a
                p = t
    ans += w[1]
    T.append(w[0])
    for ni in range(n):
        for i in range(len(A[ni])):
            if w[0] == A[ni][i][0]:
                del A[ni][i]
                break
    for ni in range(n):
        for i in range(len(A[ni])):
            if A[ni][i][0] == p:
                del A[ni][i]
                break

print(ans)

Python: #!/usr/bin/env python3


# Union find
class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parent = list(range(N))

    def root(self, x):
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  # パス圧縮
        return x

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        self.parent[self.root(x)] = self.root(y)

    def __str__(self):
        groups = {}
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result


# Kruscal法: 最小全域木
# num_vertices: int
# edges=(vertex1, vertex2, weight): List[int, int, int]
# edgesについて破壊的
def kruskal(num_vertices, edges):
    total_weight = 0
    edges.sort(key=lambda e: e[2])
    u = UnionFind(num_vertices)
    for e in edges:
        x = e[0]
        y = e[1]
        weight = e[2]
        if u.same(x, y):
            continue
        u.unite(x, y)
        total_weight += weight
    return total_weight


n = int(input())
edges = []
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(i, n):
        if row[j] != -1:
            edges.append([i, j, row[j]])
print(kruskal(n, edges))