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: # -*- coding: utf-8 -*-
'''
所要時間は、分位であった。
'''
# ライブラリのインポート
#import re #正規表現
import sys
#import heapq
import bisect
#import collections
#import math

def main():
    n = int(input())
    X = [[] for i in range(n)]
    l = []
    for i, line in enumerate(sys.stdin):
        X[i] = list(line.strip("\n").split())
        for j in range(i,n):
            c = int(X[i][j])
            if c == -1:
                continue
            else:
                r = (c,i,j)
                bisect.insort(l, r)
    
    uf = UnionFind(n)
    k = 0
    ans = 0
    count = 0
    while(count < n):
        try: tmp = l[k]
        except: break
        x = tmp[1]
        y = tmp[2]
        if not uf.same(x,y):
            uf.unite(x, y)
            ans += tmp[0] 
            count += 0
        k += 1
    print(ans)

class UnionFind:
    def __init__(self,n):
        self.p = [i for i in range(n)]
        return
    
    def root(self,x):
        while(1):
            if (self.p[x] == x): break
            y = x
            x = self.p[x]
            self.p[y] = self.p[x]
        return x

    def unite(self ,x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: return
        else:
            self.p[rx] = ry
            return 
    
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry


    
if __name__ == '__main__':
    main()

Python: # -*- coding: utf-8 -*-
"""
Created on Sat Sep 22 11:44:37 2018
ALDS1-12-A
@author: maezawa
"""
import heapq

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

adj = [[] for _ in range(n+1)]
for i in range(n):
    for j in range(i, n):
        if amat[i][j] == -1:
            continue
        adj[i+1].append([amat[i][j], j+1])
        adj[j+1].append([amat[j][i], i+1])

#print(adj)
d = [10**10]*(n+1)
h = []
heapq.heappush(h, [0, 1]) # [cost, node]
visited = [False]*(n+1)
while h:
    cost, node = heapq.heappop(h)
    if visited[node] == False and cost < d[node]:
        d[node] = cost
        visited[node] = True
        for nextnode in adj[node]:
            if visited[nextnode[1]]:
                continue
            heapq.heappush(h,nextnode)

d.pop(0)
print(sum(d))

Python: MAX = 2001


def prim(tree: [int], adjacent_list: [[int]]):
    cost = 0
    next = 0
    for l in adjacent_list:
        l[next] = MAX
    while True:
        tree.append(next)
        min_list = list()
        for t in tree:
            min_list.append(min([(v, i) for i, v in enumerate(adjacent_list[t])]))
        min_cost, i = min(min_list)
        if min_cost == MAX:
            return cost
        cost += min_cost
        for l in adjacent_list:
            l[i] = MAX
        next = i


if __name__ == '__main__':
    N = int(input())
    adjacent_list = [[int(e) if int(e) != -1 else MAX for e in input().rstrip().split()] for _ in range(N)]
    test_list = []
    print(prim(test_list, adjacent_list))

Python: n=int(input())
m = [[-1 for i in range(n)] for j in range(n)]
for i in range(n): #隣接の辺のコストを入力
  nums = list(map(int, input().split()))
  for j in range(n):
    m[i][j] = nums[j]

d=[0]+[10**9]*n
visited=[0]*n
a=0
while 1:
  u=-1
  for i in range(n):
    if not visited[i] and (u<0 or d[i]<d[u]):
      u=i
  if u<0:
    break
  visited[u]=1
  a+=d[u]
  for v in range(n):
    t=m[u][v]
    if t+1 and d[v]>t:
      d[v]=t
print(a)

Python: n = int(input())
A = []
for i in range(n):
    line = input()
    A.append([int(x) for x in line.split()])

V = set(range(n))
Vnew = {0}  # ??¨???????°???¨?????????
weight = 0

while V != Vnew:
    T = V - Vnew
    minw = float('inf')
    for u in Vnew:
        for v in T:
            w = A[u][v]
            if w != -1:
                e = (u, v)
                minw = min(minw, w)
    Vnew.add(e[1])
    weight += minw


print(weight)

Python: import sys
input = sys.stdin.readline
INF = 100100

def prim(n: int, M: list):
    ans = 0
    visited = [False] * n
    d = [INF] * n
    p = [-1] * n
    d[0] = 0
    while True:
        mincost = INF
        for i in range(n):
            if not visited[i] and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == INF:
            break
        ans += mincost
        visited[u] = True
        for v in range(n):
            if not visited[v] and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
    return ans

def main():
    n = int(input())
    M = []
    for _ in range(n):
        Mi = list(map(int, input().split()))
        M.append(Mi)
    ans = prim(n,M)
    print(ans)

if __name__ == '__main__': main()

Python: import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    inf = float('inf')
    n = int(input())
    a = []

    for i in range(n):
        line = [int(i) for i in input().split()]
        line = [i if i != -1 else inf for i in line]
        a.append(line)

    
    checked = [False] * n
    d = [inf] * n
    d[0] = 0
    checked[0] = True
    ans = 0
    nxt = 0

    for i in range(n - 1):
        for j in range(n):
            if a[nxt][j] < d[j]:
                d[j] = a[nxt][j]

        min_w = inf
        min_n = 0

        for j in range(n):
            if not checked[j] and d[j] < min_w:
                min_n = j
                min_w = d[j]

        checked[min_n] = True
        nxt = min_n
        ans += min_w

    # debug(d, locals())
    print(ans)



if __name__ == '__main__':
    solve()