Go: package main

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

const (
	WHITE int = iota
	GRAY
	BLACK
)

type graph struct {
	G [][]int
	C []int
	D []int
	P []int
}

var INFTY = 1 << 32

func constructGraph() *graph {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	g := make([][]int, n)
	c := make([]int, n)
	d := make([]int, n)
	p := make([]int, n)

	for i := 0; i < n; i++ {
		sc.Scan()
		fields := strings.Fields(sc.Text())
		g[i] = toIntSlice(fields)
	}

	return &graph{g, c, d, p}
}

func (g *graph) initMst() {
	for i := 0; i < len(g.G); i++ {
		g.C[i] = WHITE
		g.D[i] = INFTY
	}
	g.D[0] = 0
	g.P[0] = -1
}

func (g *graph) primMst() int {
	g.initMst()

	var u int
	for {
		mincost := INFTY
		for i := 0; i < len(g.G); i++ {
			if g.C[i] != BLACK && g.D[i] < mincost {
				mincost = g.D[i]
				u = i
			}
		}

		if mincost == INFTY {
			break
		}

		g.C[u] = BLACK

		for i := 0; i < len(g.G); i++ {
			if g.C[i] != BLACK && g.existEdge(u, i) {
				if g.G[u][i] < g.D[i] {
					g.D[i] = g.G[u][i]
					g.P[i] = u
				}
			}
		}
	}

	totalCost := 0
	for _, cost := range g.D {
		totalCost += cost
	}
	return totalCost
}

func (g *graph) existEdge(u, v int) bool {
	return g.G[u][v] != INFTY && g.G[v][u] != INFTY
}

func toIntSlice(s []string) []int {
	a := make([]int, len(s))
	for i, v := range s {
		num, _ := strconv.Atoi(v)
		if num == -1 {
			num = INFTY
		}
		a[i] = num
	}
	return a
}

func main() {
	g := constructGraph()
	fmt.Println(g.primMst())
}

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

Python: def prim():
    global M
    global n
    global INF
    color = ['w' for i in range(n)]
    d = [INF for i in range(n)]
    d[0] = 0
    p = [-1 for i in range(n)]

    while True:
        mincost = INF
        u = -1
        for i in range(n):
            if color[i] != 'b' and d[i] < mincost:
                mincost = d[i]
                u = i
        if u == -1:
            break
        color[u] = 'b'
        for v in range(n):
            if color[v] != 'b' and M[u][v] != INF:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = 'g'
    s = 0
    for i in range(n):
        if p[i] != -1:
            s += M[i][p[i]]
    return s


INF = 3000
n = int(input())

M = [[0 for j in range(n)] for i in range(n)]

for i in range(n):
    for j, x in enumerate(list(map(int, input().split()))):
        if x == -1:
            M[i][j] = INF
        else:
            M[i][j] = x
s = prim()
print(s)

Python: def prim():
    INFTY = float('inf')
    color = ['WHITE' for _ in range(n)]
    d = [INFTY for _ in range(n)]
    p = [None for _ in range(n)]
    d[0] = 0
    p[0] = -1

    while True:
        mincost = INFTY
        for i in range(n):
            if color[i] != 'BLACK' and d[i] < mincost:
                mincost = d[i]
                u = i
        
        if mincost == INFTY:
            break

        color[u] = 'BLACK'

        for v in range(n):
            if color[v] != 'BLACK' and A[u][v] != -1:
                if A[u][v] < d[v]:
                    d[v] = A[u][v]
                    p[v] = u
                    color[v] = 'GRAY'
    return sum(d)

n = int(input())
A = []
for _ in range(n):
    l = list(map(int, input().split()))
    A.append(l)

print(prim())