Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

const INF = 1 << 60

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	G := make([][]int, N)
	for i := 0; i < N; i++ {
		G[i] = make([]int, N)
		for j := 0; j < N; j++ {
			G[i][j] = sc.nextInt()
		}
	}
	d := make([]int, N)
	for i := 0; i < N; i++ {
		d[i] = INF
	}
	seen := make([]bool, N)
	d[0] = 0
	ans := 0
	for {
		cur := 0
		minCost := INF
		for i := 0; i < N; i++ {
			if !seen[i] && d[i] < minCost {
				minCost = d[i]
				cur = i
			}
		}
		if minCost == INF {
			break
		}
		seen[cur] = true
		ans += d[cur]
		for i := 0; i < N; i++ {
			cost := G[cur][i]
			if cost != -1 && cost < d[i] {
				d[i] = cost
			}
		}
	}

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}

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