Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	seen := make([]bool, n)
	for i := range list {
		list[i] = make([]int, n)
		for j := range list[i] {
			list[i][j] = scanInt()
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	sum := 0
	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if seen[node.id] {
			continue
		}
		seen[node.id] = true
		sum += node.weight

		for i, w := range list[node.id] {
			if w < 0 {
				continue
			}
			heap.Push(h, Node{id: i, weight: w})
		}
	}

	fmt.Println(sum)
}

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

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

for i in range(n):
    inp = input()
    if "-1" in inp:
        inp = inp.replace("-1","10000")
    a.append(list(map(int, inp.split())))

w = 0
v = set()
v.add(0)

while len(v) < n:
    min_w   = 10000
    min_idx = 0
    i = 0
    for node in v:
        if min_w > min(a[node]):
            min_w = min(a[node])
            i = node
            min_idx = a[i].index(min_w)
    if min_idx in v:
        a[i][min_idx] = 10000
        continue
    else:
        w += min_w
        v.add(min_idx)

print(w)

Python: import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

class union_find():
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

    def find_root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.find_root(self.root[x])
            return self.root[x]

    def unite(self,x,y):
        x=self.find_root(x)
        y=self.find_root(y)

        if x==y:
            return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

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

    def cnt(self,x):
        return -self.root[self.find_root(x)]

n=int(input().rstrip())
G=union_find(n)
g=[]
for k in range(n):
    a=[int(i) for i in input().split()]
    for j in range(n):
        if a[j]!=-1:
            g.append((k,j,a[j]))
g.sort(key=lambda x:x[2])
ans=0
for i in g:
    u,v,c=i
    if not G.same(u,v):
        G.unite(u,v)
        ans+=c
print(ans)

Python: from heapq import heappush, heappop

def search(v, u):
    while v != root[v]: v = root[v]
    while u != root[u]: u = root[u]
    
    return v, u

def rebuild(v, u, r):
    while v != root[v]: v, root[v] = root[v], r
    while u != root[u]: u, root[u] = root[u], r
    return v, u

n = int(input())
root = [i for i in range(n)]
depth = [1] * n

q = []

for i in range(n):
    for j, c in enumerate(list(map(int, input().split()))):
        if c == -1: continue
        heappush(q, (c, i, j))
        
ans = 0

while q:
    c, v, u = heappop(q)
    
    v_r, u_r = search(v, u)
    if v_r == u_r: continue
    
    ans += c
    
    v_d, u_d = depth[v_r], depth[u_r]
    if v_d == u_d:
        depth[v_r] += 1
        if depth[v_r] > 10: rebuild(v, u, v_r)
        
    elif v_d < u_d: v_r, u_r = u_r, v_r
    
    root[v_r] = u_r
    
print(ans)

Python: class Forest:
    def __init__(self, g, id):
        self.forest = set([id])
        self.graph = g
        self.next_wait = self.graph[id]
        self.wait = 0
    def add_tree(self, id):
        self.wait += self.next_wait[id]
        self.forest.update([id])
         
        self.marge_next_wait(id)
    def next_tree(self):
        min_id = min_wait = None
        for id, wait in self.next_wait.items():
            if id not in self.forest:
                if min_wait == None or min_wait > wait:
                    min_wait = wait
                    min_id = id
        return min_id
    def marge_next_wait(self, merge_id):
        for id, wait in self.graph[merge_id].items():
            if id not in self.next_wait or self.next_wait[id] > wait:
                self.next_wait[id] = wait
n = int(input())
g = [{e:i for e, i in enumerate(map(int, input().split())) if i != -1} for _ in range(n)]
forest = Forest(g,0)
for i in range(n - 1):
    id = forest.next_tree()
    forest.add_tree(id)
print(forest.wait)

Python: n = int(input())
M = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(n):
 L = list(map(int, input().split()))
 for j,v in enumerate(L):
  if v != -1:
   M[i][j] = v

def prim():
 color = [0] * n
 d = [float("inf")] * n
 d[0] = 0

 while True:
  minv = float("inf")
  u = -1
  for i in range(n):
   if minv > d[i] and color[i] != 2:
    u = i
    minv = d[i]
  if u == -1: break
  color[u] = 2
  for v in range(n):
   if color[v] != 2 and M[u][v] != float("inf"):
    if d[v] > M[u][v]:
     d[v] = M[u][v]
 return sum(d)

print(prim())

Python: from sys import stdin
INF = float('inf')
WHITE, GRAY, BLACK = 0, 1, 2
n = int(stdin.readline())
M = [[INF] * n for _ in range(n)]
for i in range(0, n):
    for j, e in enumerate(list(map(int, stdin.readline().split()))):
        if e != -1: M[i][j] = e
d = [INF] * n
d[0] = 0
color = [0] * n
def prim():
    while True:
        minv = INF
        u = -1
        for i in range(0, 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(0, n):
            if color[v] != BLACK and d[v] > M[u][v]:
                d[v] = M[u][v]
    return sum(d)
print(prim())