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

Python: INF = float('inf')
N = int(input())
M = []
D = []
P = []
visited = []
for i in range(N):
    M.append([a if a != -1 else INF for a in map(int, input().split())])
    D.append(INF)
    P.append(-1)
    visited.append(False)

D[0] = 0
P[0] = None

while True:
    min_cost = INF
    u = -1
    for i in range(N):
        if not visited[i] and D[i] < min_cost:
            u = i
            min_cost = D[i]

    if u == -1:
        break

    visited[u] = True

    for i, m in enumerate(M[u]):
        if not visited[i] and m != INF and m < D[i]:
            D[i] = m
            P[i] = u

print(sum(D))

Python: n = int(input())
a = []
lrg = 2000000
for i in range(n):
    tmp = list(map(int, input().split( )))
    for j in range(n):
        if tmp[j] == -1:
            tmp[j] = lrg
    a.append(tmp)
#for i in range(n):
#    print(*a[i])
V = [0]
T = []
weight = 0

while len(V)<n:
    mn = lrg-1###forの外
    tmp = -1###forの外
    for v in V:
        for i in range(n):
            if i not in V and mn>a[v][i]:
                mn = a[v][i]
                tmp = i
    weight += mn
    #print(v,[v,tmp])
    V.append(tmp)
    #print(*V)

print(weight)

Python: n = int(input())
a = []
b = []
c = []

def root(x):
    global rs
    if rs[x] == x:
        return(x)
    else:
        return(root(rs[x]))

for _ in range(n):
    a.append(list(map(int,input().split())))
for i in range(n):
    for j in range(i+1,n):
        if a[i][j] >= 0:
            b.append([a[i][j],i,j])
rs = [(i) for i in range(n)]

b.sort()
ans = 0
while(len(b)):
    if root(b[0][1]) != root(b[0][2]):
        ans += b[0][0]
        rs[root(rs[b[0][2]])] = root(b[0][1])
        c.append(b[0])
    del(b[0])
print(ans)