Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

const INF = 1 << 60

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	G := make([][]int, N)
	for i := 0; i < N; i++ {
		G[i] = make([]int, N)
		for j := 0; j < N; j++ {
			G[i][j] = sc.nextInt()
		}
	}
	d := make([]int, N)
	for i := 0; i < N; i++ {
		d[i] = INF
	}
	seen := make([]bool, N)
	d[0] = 0
	ans := 0
	for {
		cur := 0
		minCost := INF
		for i := 0; i < N; i++ {
			if !seen[i] && d[i] < minCost {
				minCost = d[i]
				cur = i
			}
		}
		if minCost == INF {
			break
		}
		seen[cur] = true
		ans += d[cur]
		for i := 0; i < N; i++ {
			cost := G[cur][i]
			if cost != -1 && cost < d[i] {
				d[i] = cost
			}
		}
	}

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}

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

Python: import itertools

n = int(input())
A = [list(map(int, input().strip().split(' '))) for _ in range(n)]
uvc = [] # A list of tuples of start, end, and cost
for i in range(n-1):
    for j in range(i+1, n):
        if A[i][j] >= 0:
            uvc.append((i, j, A[i][j]))

# コストでソート
uvc.sort(key=lambda x: x[2])

uf = list(range(n))

def find_root(x):
    global uf
    if x == uf[x]:
        return x
    else:
        uf[x] = find_root(uf[x])
        return uf[x]

def union(x, y):
    global uf
    uf[find_root(x)] = find_root(y)

def is_same_set(x, y):
    return find_root(x) == find_root(y)

def costs():
    global uvc
    for u, v, c in uvc:
        if not is_same_set(u, v):
            union(u, v)
            yield c
print(sum(itertools.islice(costs(), n - 1)))

Python: class UnionFind:
    def __init__(self, n: int):
        self.nodes = n
        self.parents = [-1] * n
        self.rank = [0] * n

    # retrun the root of element x
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # unite the group include element x and group include element y
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # get size of the gourp which element x belongs
    def get_size(self, x):
        return -self.parents[self.find(x)]

    # check if element x and element y is same group
    def same(self, x, y):
        return self.find(x) == self.find(y)


def kruskal(n: int, edges: list):
    """
    n: count of nodes
    edges: list of edges, format: (node1,node2,weight)
    """
    union = UnionFind(n + 1)  # 1-indexed
    mst_sum = 0
    mst = []
    for edge in edges:
        n1, n2, w = edge
        if not union.same(n1, n2):
            union.unite(n1, n2)
            mst_sum += w
            mst.append(edge)
    return mst, mst_sum


n = int(input())
graph_table = []

for _ in range(n):
    graph_table.append([int(i) for i in input().split()])

edges = []
# edge一覧を取得
for i in range(n - 1):
    for j in range(i + 1, n):
        if graph_table[i][j] != -1:
            edges.append((i, j, graph_table[i][j]))  # node1,node2,weight

# edgeを重みの昇順にソート
edges = sorted(edges, key=lambda x: x[2])

_, mst_sum = kruskal(n, edges)
print(mst_sum)

Python: n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
m = [2001] * n
f = [0] * n
sum = 0

m[0] = 0
f[0] = 1
v = 0

for i in range(n-1) :
    for j in range(n) :
        if (a[v][j] < m[j]) & (f[j] == 0) & (a[v][j] != -1):
            m[j] = a[v][j]
    
    min = 2001
    minj = 0
    for j in range(n) :
        if (m[j] < min) & (f[j] == 0):
            min = m[j]
            minj = j
    
    v = minj
    f[minj] = 1
    sum += min

print(sum)