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: import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


class UnionFind:
    def __init__(self,arg_V):
        self.V = arg_V
        self.boss = [None]*arg_V
        self.height = [None]*arg_V

    def init(self):
        for i in range(self.V):
            self.boss[i] = i
            self.height[i] = 0

    def get_boss(self,index):
        if index == self.boss[index]:
            return index
        else:
            self.boss[index] = self.get_boss(self.boss[index])
            return self.boss[index]


    def is_same_group(self,a,b):
        return self.get_boss(a) == self.get_boss(b)

    def unite(self,x,y):
        boss_x = self.get_boss(x)
        boss_y = self.get_boss(y)

        if boss_x == boss_y:
            return

        if self.height[x] > self.height[y]:

            self.boss[boss_y] = boss_x

        elif self.height[x] < self.height[y]:

            self.boss[boss_x] = boss_y

        else:
            self.boss[boss_y] = boss_x
            self.height[x] += 1

class Edge:
    def __init__(self,arg_FROM,arg_TO,arg_WEIGHT):
        self.FROM = arg_FROM
        self.TO = arg_TO
        self.WEIGHT = arg_WEIGHT

    def __lt__(self,arg):
        return self.WEIGHT < arg.WEIGHT


V = int(input())

TABLE = []
for i in range(V):
    input_array = list(map(int,input().split()))
    for k in range(len(input_array)):
        if input_array[k] != -1:
            TABLE.append(Edge(i,k,input_array[k]))

UF = UnionFind(V)
UF.init()

TABLE.sort()

ans = 0

for i in range(len(TABLE)):
    if UF.is_same_group(TABLE[i].FROM, TABLE[i].TO) == False:
        UF.unite(TABLE[i].FROM, TABLE[i].TO)
        ans += TABLE[i].WEIGHT

print("%d"%(ans))

Python: #!/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}
    gravity = 0

    while g:
        minimum = maxint
        for j in h:
            for i, a in enumerate(M[j-1], 1):
                if i in h:
                    continue
                if 0 < a < minimum:
                    index = i
                    minimum = a
        h.add(index)
        g.remove(index)
        gravity += minimum

    print(gravity)


main()

Python: n = int(input())
edge = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(i + 1, n):
        if a[j] != -1:
            edge.append((a[j], i, j))
edge.sort()
ans = 0

tree = [i for i in range(n)]
def root(x):
    pre = []
    while x != tree[x]:
        pre.append(x)
        x = tree[x]
    for node in pre:
        tree[node] = x
    return x
def unite(x, y):
    X, Y = root(x), root(y)
    if X != Y:
        tree[X] = Y

for cost, x, y in edge:
    X, Y = root(x), root(y)
    if X != Y:
        ans += cost
        tree[X] = Y
print(ans)

Python: import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
M = []

def prim(G, root, n):
    BLACK = 1<<10
    WHITE = 1<<20
    nodes = [WHITE] * n
    d = [INF] * n
    d[root] = 0
    p = [0] * n
    p[root] = -1
    while True:
        mincost = INF

        # 探索
        for i in range(n):
            if d[i] < mincost and nodes[i] == WHITE:
                mincost = d[i]
                next = i
        if mincost == INF:
            break
        # 移動
        nodes[next] = BLACK

        # 伝播
        for i in range(n):
            if nodes[i] == WHITE and G[next][i] != INF:
                if G[next][i] < d[i]:
                    d[i] = G[next][i]
                    p[i] = next
    return d

def main():
    global M
    n = int(input().strip())
    M = [[0] * n for _ in range(n)]
    for i in range(n):
        M[i] = list(map(lambda x: INF if x == -1 else x, map(int, input().strip().split())))
    d = prim(M, 0, n)
    print(sum(d))

if __name__ == '__main__':
    main()

Python: # -*- coding: utf-8 -*-
from heapq import heappop, heappush


def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):
    '''
    Returns the Minimum Spanning Tree(MST) of a given graph

    # sample input when given not as adjacency list (adj_matrix=False) (generally works faster)
    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0
             [(0, 2), (3, 3), (4, 6)],         # node 1
             [(0, 5), (3, 2), (5, 6)],         # node 2
             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3
             [(1, 6), (3, 2), (5, 4)],         # node 4
             [(2, 6), (4, 4)]]                 # node 5

    # sample input when given as adjacency matrix (adj_matrix=True)
    edges = [[0, 2, 5, 4, inf, inf],           # node 0
             [2, 0, inf, 3, 6, inf],           # node 1
             [5, inf, 0, 2, inf, 6],           # node 2
             [4, 3, 2, 0, 2, inf],             # node 3
             [inf, 6, inf, 2, 0, 4],           # node 4
             [inf, inf, 6, inf, 4, 0]]         # node 5
    '''

    n = len(edges)

    costs = [float('inf')] * n
    costs[start] = 0
    prevs = [-1] * n

    pq = [(0, start)]
    T = [True] * n

    while pq:
        tmp_cost, tmp_node = heappop(pq)
        T[tmp_node] = False

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value and T[node]) if adj_matrix else\
                    ((node, cost) for node, cost in edges[tmp_node] if T[node])

        for nxt_node, nxt_cost in nxt_edges:
            if costs[nxt_node] > nxt_cost:
                costs[nxt_node] = nxt_cost
                prevs[nxt_node] = tmp_node
                heappush(pq, (nxt_cost, nxt_node))
                T[nxt_node] = True

    else:
        if len([prev for prev in prevs if prev != -1]) != n - 1:
            raise NoSpanningError(
                'There is no spanning tree in this graph (search started from node{})'.
                format(start))

        else:
            return prevs, costs


class NoSpanningError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_A
    '''

    n = int(input())
    edges = [[(j, int(cost)) for j, cost in enumerate(input().split())
              if int(cost) != -1] for i in range(n)]

    prevs, costs = prim(edges)
    print(sum(costs))