Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	g := make([][]int, n)
	ans := make([][]int, n)

	inf := 1 << 30
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		ans[i] = make([]int, n)
		for ii := 0; ii < n; ii++ {
			g[i][ii] = getNextInt(scanner)
			if g[i][ii] == -1 {
				g[i][ii] = inf
			}
			ans[i][ii] = -1
		}
	}

	im := make(IntMap, 1)

	im.increment(1)

	for len(im) < n {
		min := inf
		u := -1
		v := -1
		for i := range im {
			for ii := 0; ii < n; ii++ {
				if im.get(ii) != 0 {
					continue
				}
				if min > g[i][ii] {
					min = g[i][ii]
					u = i
					v = ii
				}
			}
		}
		im.increment(v)
		ans[u][v] = min
		ans[v][u] = min
	}

	sum := 0
	for i := 0; i < n-1; i++ {
		for ii := i + 1; ii < n; ii++ {
			if ans[i][ii] != -1 {
				sum += ans[i][ii]
			}
		}
	}

	fmt.Fprintln(writer, sum)
	writer.Flush()
}

// IntMap ...
type IntMap map[int]int

func (m IntMap) get(key int) int {
	if _, ok := m[key]; ok {
		return m[key]
	}
	return 0
}
func (m IntMap) increment(key int) {
	if _, ok := m[key]; ok == false {
		m[key] = 0
	}
	m[key]++
}

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)