Go: package main

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

const (
	white int = iota
	gray
	black
)
const INFTY int = 2001

var G [][]int
var color []int
var d []int
var p []int
var N int

func prim() int {
	u := 0
	d[u] = 0
	for {
		minCost := INFTY
		for i:=0; i<N; i++ {
			if color[i] != black && d[i] < minCost {
				minCost = d[i]
				u = i
			}
		}

		if minCost == INFTY {
			break
		}

		color[u] = black

		for v:=0; v<N; v++ {
			if color[v] != black && G[u][v] != -1 {
				if G[u][v] < d[v] {
					d[v] = G[u][v]
					p[v] = u
					color[v] = gray
				}
			}
		}
	}
	// sum
	sum := 0
	for i:=0; i<N; i++ {
		if p[i] != -1 {
			sum += G[i][p[i]]
		}
	}
	return sum
}




func initVariable(N int) {
	G = make([][]int, N)
	for i:=0; i<N; i++ {
		G[i] = make([]int, N)
	}
	color = make([]int, N)
	d = make([]int, N)
	p = make([]int, N)
	for i:=0; i<N; i++ {
		d[i] = INFTY
		p[i] = -1
	}
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	N = nextInt(scanner)
	initVariable(N)
	for i:=0; i<N; i++ {
		for j:=0; j<N; j++ {
			G[i][j] = nextInt(scanner)
		}
	}
	fmt.Printf("%d\n", prim())
}

Python: n=int(input())
M=[list(map(int,input().split()))for _ in[0]*n]
d=[0]+[1e4]*~-n
p=[-1]*n
b=[1]*n
while 1:
 m,u=1e4,-1
 for i in range(n):
  if m>d[i]and b[i]:m,u=d[i],i
 if u<0:break
 b[u]=0
 for v in range(n):
  if b[v]and 1+M[u][v]and d[v]>M[u][v]:
   d[v],p[v]=M[u][v],u
print(sum(M[i][p[i]]for i in range(n)if p[i]+1))

Python: import sys
def prim(n, m):
	d = [sys.maxsize]*n
	p = [-1]*n
	c = [False]*n
	d[0] = 0
	while True:
		minv = sys.maxsize
		u = -1
		for i in range(n):
			if minv > d[i] and c[i] == False:
				minv = d[i]
				u = i
		if u == -1:
			break
		c[u] = True
		for i in range(n):
			if m[u][i] != sys.maxsize:
				if m[u][i] < d[i] and c[i] == False:
						d[i] = m[u][i]
						p[i] = u
	sum = 0
	for i in range(n):
		if p[i] != -1:
			sum += m[i][p[i]]
	return sum

n = int(input())
m = [[0 for x in range(n)] for x in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	for j in range(n):
		if a[j] == -1:
			m[i][j] = sys.maxsize
		else:
			m[i][j] = a[j]
print(prim(n, m))

Python: import heapq

n = int(input())
A = [[int(i) for i in input().split()] for i in range(n)]
h = []
DP = {}
heapq.heappush(h,(0,0))
c = 0
while(len(DP)<n):
    tmp = heapq.heappop(h)
    if tmp[1] in DP:
        continue
    c += tmp[0]
    DP[tmp[1]] = 1
    for i,j in enumerate(A[tmp[1]]):
        if j > 0 and not i in DP:
            heapq.heappush(h,(j,i))
print(c)

Python: n=int(input())
M=[list(map(int,input().split()))for _ in[0]*n]
d=[0]+[1e4]*~-n
p=[-1]*n
b=[1]*n
while 1:
 m,u=1e4,-1
 for i in range(n):
  if m>d[i]and b[i]:m,u=d[i],i
 if u<0:break
 b[u]=0
 for v in range(n):
  if b[v]and 1+M[u][v]and d[v]>M[u][v]:
   d[v],p[v]=M[u][v],u
print(sum(M[i][p[i]]for i in range(n)if p[i]+1))

Python: # -*- coding: utf-8 -*-


if __name__ == '__main__':

    n = int(input())
    M = [list(map(int, input().split(" ")[1:])) for _ in range(n)]

    color = [0] * n
    d = [float("inf")] * n
    p = [None] * n

    def prim():
        d[0] = 0
        p[0] = -1

        while True:
            mincost = float("inf")
            for i in range(n):
                if color[i] != 2 and d[i] < mincost:
                    mincost = d[i]
                    u = i

            if mincost == float("inf"):
                break

            color[u] = 2

            for v in range(n):
                if color[v] != 2 and M[u][v] != -1:
                    if M[u][v] < d[v]:
                        d[v] = M[u][v]
                        p[v] = u
                        color[v] = 1

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

    print(sum)

Python: def kruskal(edges):
    edges.sort(key=lambda pair:pair[2])
    uf_tree = UnionFindTree(n_node)
    total_cost = 0
    for i, j, cost in edges:
        if cost < 0:
            continue

        if not uf_tree.have_same_root(i, j):
            uf_tree.unite(i, j)
            total_cost += cost
    return total_cost


class UnionFindTree:
    def __init__(self, n_node):
        self.parent = [i for i in range(n_node)]
        self.rank = [0] * n_node

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

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

        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
            else:
                self.parent[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def have_same_root(self, x, y):
        return self.find(x) == self.find(y)

if __name__ == "__main__":
    n_node = int((input()))
    edges = []
    for i in range(n_node):
        for j, cost in enumerate(map(int, input().split())):
            edges.append((i, j, cost))

    print(kruskal(edges))

Python: class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


class Kruskal:
    """ Kruskal's algorithm: find minimum spanning tree
        Complexity: O(E log(V))
        used in GRL2A(AOJ)
    """

    def __init__(self, V, E, start=0, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (undirected graph)
        """
        self.kruskal(V, E)

    def kruskal(self, V, E):
        edges = []
        for v1 in range(V):
            for v2, cost in E[v1]:
                if v1 < v2:
                    edges.append((cost, v1, v2))
        edges.sort(reverse=True)
        self.mincost = 0
        self.minSpanningTree = []
        uf = UnionFindTree(V)
        while len(self.minSpanningTree) < V-1:
            cost, v1, v2 = edges.pop()
            if uf.same(v1, v2) == False:
                self.mincost += cost
                uf.unite(v1, v2)
                self.minSpanningTree.append((v1, v2, cost))

    def minCost(self):
        return self.mincost

    def getMinSpanningTree(self):
        return sorted(self.minSpanningTree)

V = int(input())
edge = [[] for _ in range(V)]
for i in range(V):
    for j, d in enumerate(map(int, input().split())):
        if d != -1:
            edge[i].append((j, d))
mst = Kruskal(V, edge)
print(mst.minCost())

Python: from sys import stdin
INF = 1<<21
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())