Go: package main

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

const (
	WHITE int = iota
	GRAY
	BLACK
)

type graph struct {
	G [][]int
	C []int
	D []int
	P []int
}

var INFTY = 1 << 32

func constructGraph() *graph {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	g := make([][]int, n)
	c := make([]int, n)
	d := make([]int, n)
	p := make([]int, n)

	for i := 0; i < n; i++ {
		sc.Scan()
		fields := strings.Fields(sc.Text())
		g[i] = toIntSlice(fields)
	}

	return &graph{g, c, d, p}
}

func (g *graph) initMst() {
	for i := 0; i < len(g.G); i++ {
		g.C[i] = WHITE
		g.D[i] = INFTY
	}
	g.D[0] = 0
	g.P[0] = -1
}

func (g *graph) primMst() int {
	g.initMst()

	var u int
	for {
		mincost := INFTY
		for i := 0; i < len(g.G); i++ {
			if g.C[i] != BLACK && g.D[i] < mincost {
				mincost = g.D[i]
				u = i
			}
		}

		if mincost == INFTY {
			break
		}

		g.C[u] = BLACK

		for i := 0; i < len(g.G); i++ {
			if g.C[i] != BLACK && g.existEdge(u, i) {
				if g.G[u][i] < g.D[i] {
					g.D[i] = g.G[u][i]
					g.P[i] = u
				}
			}
		}
	}

	totalCost := 0
	for _, cost := range g.D {
		totalCost += cost
	}
	return totalCost
}

func (g *graph) existEdge(u, v int) bool {
	return g.G[u][v] != INFTY && g.G[v][u] != INFTY
}

func toIntSlice(s []string) []int {
	a := make([]int, len(s))
	for i, v := range s {
		num, _ := strconv.Atoi(v)
		if num == -1 {
			num = INFTY
		}
		a[i] = num
	}
	return a
}

func main() {
	g := constructGraph()
	fmt.Println(g.primMst())
}

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)

Python: def solv(G):
  n = len(G)
  V = {0:0}
  new_V = []
  cost = 0

  while len(new_V) < n:
    u, e = min(V.items(), key=lambda x:x[1])
    V.pop(u)
    new_V.append(u)
    cost += e
    for v, e in enumerate(G[u]):
      if e < 0 or v == u or v in new_V: continue
      V[v] = min(V[v], e) if v in V else e

  return cost

n = int(input())
G = [list(map(int, input().split())) for _ in range(n)]
print(solv(G))

Python: import heapq

n = int(input())
edges = [set((w, j) for j, w in enumerate(map(int, input().split())) if w > -1) for _ in range(n)]

visited = [False] * n
visited[0] = True
queue = list(edges[0])
heapq.heapify(queue)
total_cost, remains = 0, n - 1
while True:
    cost, vertex = heapq.heappop(queue)
    if visited[vertex]:
        continue
    visited[vertex] = True
    total_cost += cost
    remains -= 1
    if not remains:
        break
    for t in edges[vertex]:
        if not visited[t[1]]:
            heapq.heappush(queue, t)

print(total_cost)

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)