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: class UnionFindTree:
    """
        Disjoint set data structure
        Union-Find tree
        complexity:
            init: O(n)
            find, unite, same: O(alpha(n))
    """
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n

    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
        elif 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 logV)
    """
    def __init__(self, V, E, start=0, INF=10**9):
        """
        :param V: the number of vertices
        :param E:  adjacency list (undirected graph)
        :param start:
        :param INF:
        """
        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.min_spanning_tree = []
        uf = UnionFindTree(V)
        while len(self.min_spanning_tree) < V - 1:
            cost, v1, v2 = edges.pop()
            if not uf.same(v1, v2):
                self.mincost += cost
                uf.unite(v1, v2)
                self.min_spanning_tree.append((v1, v2, cost))

    def min_cost(self):
        return self.mincost

    def get_min_spanning_tree(self):
        return sorted(self.min_spanning_tree)


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

Python: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
 
 
def main():
    num = int(stdin.readline())
 
    M = []
    for _ in xrange(num):
        M.append([int(s) for s in stdin.readline().split()])
 
    g = set(xrange(1, num+1))
    index = g.pop()
    h = {index}
    weight = 0
 
    while g:
        minimum = maxint
        for j in h:
            mj = M[j-1]
            for i in g:
                if 0 <= mj[i-1] < minimum:
                    index = i
                    minimum = mj[i-1]
        h.add(index)
        g.remove(index)
        weight += minimum
 
    print(weight)

Python: #!/usr/bin/python3
import itertools

n = int(input())
A = []
for i in range(n):
    src = input()
    dst = src.replace('-1', '3000')
    ai = list(map(int, dst.split()))
    A.append(ai)
# rand
i = 0
S = 0
G = set()
T = set(range(n))

T.remove(i)
G.add(i)

while len(T) > 0:
    m = 3000
    mg = None
    mt = None
    for g, t in itertools.product(G, T):
        if A[g][t] < m:
            mg = g
            mt = t
            m = A[g][t]
    S += m
    G.add(mt)
    T.remove(mt)

print(S)

Python: import array
import collections
import heapq

INF = 1e9

N = int(input())

AdjacentVertex = collections.namedtuple('AdjacentVertex', 'vertex cost')
adjacency_list = collections.defaultdict(set)

NO_VERTEX = -1
 
def compute_mst_prim(max_v, adj_list):
    pred = collections.defaultdict(lambda: NO_VERTEX)
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)

for i in range(N):
    u = list(map(int, input().split()))
    for j in range(N):
        if u[j] == -1:
            adjacency_list[i].add(AdjacentVertex(j, INF))
            adjacency_list[j].add(AdjacentVertex(i, INF))
        else:
            adjacency_list[i].add(AdjacentVertex(j, u[j]))
            adjacency_list[j].add(AdjacentVertex(i, u[j]))

(_, key) = compute_mst_prim(N, adjacency_list)

print(sum(key.values()))

Python: import heapq
from collections import defaultdict
v_num = int(input())
edges = defaultdict(list)
for i in range(v_num):
    data = [int(n) for n in input().split(" ")[1:]]
    for j in range(i + 1, v_num):
        if data[j] != -1:
            edges[i].append([data[j], j])
            edges[j].append([data[j], i])
queue = []
heapq.heapify(queue)
for c in edges[0]:
    heapq.heappush(queue, c)
visited = {0}
answer = 0
while len(visited) < v_num:
    q = heapq.heappop(queue)
    weight, one = q[0], q[1]
    if one in visited:
        continue
    answer += weight
    for e in edges[one]:
        if e[1] not in visited:
            heapq.heappush(queue, e)
    visited |= {one}
print(answer)

Python: import sys
INF = float('inf')
n = int(input())
adja_matrix = [[int(i) for i in line.split()] for line in sys.stdin.read().splitlines()]
condition = ['INIT'] * n
distance = [INF] * n
p = [0] * n
distance[0] = 0
p[0] = -1

while True:
    mincost = INF
    for i in range(n):
        if condition[i] != 'FINISH' and distance[i] < mincost:
            mincost = distance[i]
            u = i

    if mincost == INF:
        break

    condition[u] = 'FINISH'

    for v in range(n):
        if condition[i] != 'FINISH' and adja_matrix[u][v] != -1:
            if adja_matrix[u][v] < distance[v]:
                distance[v] = adja_matrix[u][v]
                p[v] = u
                condition[v] = 'CHECK'

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

print(sum)