Go: package main

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

const BIG_COST = 3000

const (
	ST_NOT_YET = iota
	ST_JOINED
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	nNodes := scanInt(sc)
	costs := make([][]int, nNodes)

	for r := 0; r < nNodes; r++ {
		costs[r] = make([]int, nNodes)
		for c := 0; c < nNodes; c++ {
			costs[r][c] = scanInt(sc)
		}
	}

	states := make([]int, nNodes)
	minCosts := make([]int, nNodes)

	for i := 1; i < nNodes; i++ {
		minCosts[i] = BIG_COST
	}

	for {
		var u int
		minCost := BIG_COST

		for i := 0; i < nNodes; i++ {
			if states[i] != ST_JOINED && minCosts[i] < minCost {
				minCost = minCosts[i]
				u = i
			}
		}

		// 全てのノードが MST に JOIN できたので終了。
		if minCost == BIG_COST {
			break
		}

		states[u] = ST_JOINED

		for v := 0; v < nNodes; v++ {
			cost := costs[u][v]

			// MST内の u と MST外の v との辺の重みをそれぞれ minCosts[v] として
			// 保存しておく。このうち辺の重みが最小となる v が次のループで MST に JOIN する。
			if states[v] != ST_JOINED && cost != -1 && cost < minCosts[v] {
				minCosts[v] = cost
			}
		}
	}

	sum := 0
	for _, cost := range minCosts {
		sum += cost
	}
	fmt.Println(sum)
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

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