Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	seen := make([]bool, n)
	for i := range list {
		list[i] = make([]int, n)
		for j := range list[i] {
			list[i][j] = scanInt()
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	sum := 0
	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if seen[node.id] {
			continue
		}
		seen[node.id] = true
		sum += node.weight

		for i, w := range list[node.id] {
			if w < 0 {
				continue
			}
			heap.Push(h, Node{id: i, weight: w})
		}
	}

	fmt.Println(sum)
}

Python: n = int(input())
A = [list(map(int, input().split())) for i in range(n)]

isVisited = [False] * n
d = [0] + [2001] * (n - 1)
p = [-1] * n

while True:
    mincost = 2001
    for i in range(n):
        if (not isVisited[i]) and (d[i] < mincost):
            mincost = d[i]
            u = i

    if mincost == 2001:
        break

    isVisited[u] = True

    for v in range(n):
        if (not isVisited[v]) and (A[u][v] != -1): #uと繋がる頂点v
            if A[u][v] < d[v]:
                d[v] = A[u][v]
                p[v] = u

print(sum(d))

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