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())
G = [[] for i in range(N)]
for v in range(N):
    for w, c in enumerate(map(int, input().split())):
        if c != -1:
            G[v].append((w, c))

from heapq import heappush, heappop, heapify
used = [0]*N
que = [(c, w) for w, c in G[0]]
used[0] = 1
heapify(que)

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for w, c in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))
print(ans)

Python: n = int(input())
m = [[-1 for i in range(n)] for j in range(n)] #お隣さんへのコストを保存（この中から最小を探す）

v = set()
v.add(0)

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


def prim_mst(n):
  isVisited = [False] * n
  d = [0] + [2001] * (n-1)      #TとV-Tのを繋ぐ最小辺の重みを格納する

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


    if mincost == 2001:        #mincostが2001になったら繰り返し作業終了
      break

    for v in range (n):
      if (not isVisited[v]) and (m[u][v] != -1):
        if m[u][v] < d[v]:
          d[v] = m[u][v]
  print(sum(d))

prim_mst(n)

Python: n = int(input())
A = [[int(i) for i in input().split(" ")] for j in range(n)]

dp1={}

for i in range(n):
    for j in range(n):
        if A[i][j] != -1 :
            dp1[(i,j)] = A[i][j]
key = []
value = []
for i,j in sorted(dp1.items(), key=lambda x:x[1]):
    key.append(i)
    value.append(j)

c_v = []
N = len(key)
len_c_v = 0
ans = 0
itr = 0
while itr != N:
    if len_c_v == n:
        break
    i = key[itr][0]
    j = key[itr][1]
    if (i in c_v) == False and (j in c_v) == False:
        c_v.append(i)
        c_v.append(j)
        ans += value[itr]
        len_c_v += 2
        itr += 1
    elif (i in c_v) == False:
        c_v.append(i)
        ans += value[itr]
        itr += 1
        len_c_v += 1
    elif (j in c_v) == False:
        c_v.append(j)
        ans += value[itr]
        itr += 1
        len_c_v += 1
    else:
        itr += 1


if len_c_v != n:
    print(-1)
else:
    print(ans)

Python: def prim(cost):
    sumcost=0
    V=len(cost)
    mincost=[float('inf')] * V
    used=[False] * V
    mincost[0]=0
    while True:
        v=-1
        for u in range(V):
            if not used[u] and (v==-1 or mincost[u]<mincost[u]):
                v=u
        if v==-1: break
        used[v]=True
        sumcost=sumcost+mincost[v]
        for u in range(V):
            if cost[u][v]==-1:
                continue
            mincost[u]=min(mincost[u],cost[v][u])
    return sumcost


n=int(raw_input())
A=[0]*n
for u in range(n):
    A[u]=map(int, raw_input().split())
 
result=prim(A)
print(result)

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

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: def Serch():
    unit = [2001]
    for j in Tree:
        for i in range(1, n):
            if G[j][i] != -1 and i not in Tree:
                unit.append(G[j][i])
    for j in Tree:
        for i in range(1, n):
            if G[j][i] == min(unit) and i not in Tree:
                ans.append(int(G[j][i]))
                Tree.append(i)
                Serch()
                break


n = int(input())
G = []
for i in range(n):
    G.append(input().split())
    for j in range(len(G[i])):
        G[i][j] = int(G[i][j])

ans = []
Tree = [0]
Serch()
print(sum(ans))