Go: package main

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

const (
	white int = iota
	gray
	black
)
const INFTY int = 2001

var G [][]int
var color []int
var d []int
var p []int
var N int

func prim() int {
	u := 0
	d[u] = 0
	for {
		minCost := INFTY
		for i:=0; i<N; i++ {
			if color[i] != black && d[i] < minCost {
				minCost = d[i]
				u = i
			}
		}

		if minCost == INFTY {
			break
		}

		color[u] = black

		for v:=0; v<N; v++ {
			if color[v] != black && G[u][v] != -1 {
				if G[u][v] < d[v] {
					d[v] = G[u][v]
					p[v] = u
					color[v] = gray
				}
			}
		}
	}
	// sum
	sum := 0
	for i:=0; i<N; i++ {
		if p[i] != -1 {
			sum += G[i][p[i]]
		}
	}
	return sum
}




func initVariable(N int) {
	G = make([][]int, N)
	for i:=0; i<N; i++ {
		G[i] = make([]int, N)
	}
	color = make([]int, N)
	d = make([]int, N)
	p = make([]int, N)
	for i:=0; i<N; i++ {
		d[i] = INFTY
		p[i] = -1
	}
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	N = nextInt(scanner)
	initVariable(N)
	for i:=0; i<N; i++ {
		for j:=0; j<N; j++ {
			G[i][j] = nextInt(scanner)
		}
	}
	fmt.Printf("%d\n", prim())
}

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
        print(adjacent_list)
        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: INF = float("inf")
def MAIN():
    n = int(input())
    ans = [0] * n
    li = [INF] * n
    li[0] = 0
    A = {}
    for i in range(n):
        A[i] = {k:v for k, v in enumerate(map(int, input().split())) if v != -1}
    dp = [0]
    while dp:
        a = dp.pop()
        for k, v in A[a].items():
            if li[k] > li[a] + v:
                li[k] = li[a] + v
                ans[k] = v
                dp.append(k)
    print(sum(ans))
MAIN()

Python: from __future__ import division, print_function
from sys import stdin, maxint
 
 
def main():
    n = int(stdin.readline())
 
    M = []
    for _ in xrange(n):
        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
 
  
 
 
main()

Python: def main():

    N = 100

    n = int(input())
    adj = [[0 for i in range(n)] for j in range(n)]

    for i in range(n):
        tmp = list(map(int, input().split()))
        u = tmp[0]
        u = u -1
        k = tmp[1]
        v = tmp[2:]
        for j in range(k):
            adj[u][v[j]-1] = 1

    for i in range(n):
        for j in range(n):
            print(adj[i][j], end=" ")
        print()
    return 0

if __name__ == "__main__":
    main()

Python: class UnionFind:
  def __init__(self, v):
    # number of vertices
    self.v = v
    # parents of each node
    self.parents = [None] * v
    # heights of each node
    self.height = [None] * v

  def init(self):
    for i in range(self.v):
      self.parents[i] = i
      self.height[i] = 0

  def find(self, p):
    # finds the group containing p and return the position of its leader
    if self.parents[p] != p:
      self.parents[p] = self.find(self.parents[p])
    return self.parents[p]

  def union(self, p, q):
    parent_p = self.find(p)
    parent_q = self.find(q)

    if parent_p == parent_q: return

    if self.height[p] > self.height[q]:
      self.parents[q] = parent_p
    elif self.height[p] < self.height[q]:
      self.parents[p] = parent_q
    else:
      self.parents[parent_q] = parent_p
      self.height[p] += self.height[q]

  def same(self, p, q):
    return self.find(p) == self.find(q)

class Edge:
  def __init__(self, f, to, cost):
    self.f = f
    self.to = to
    self.cost = cost

  def __lt__(self, arg):
    return self.cost < arg.cost

n = int(input())
edges = []
for i in range(n):
  input_array = list(map(int, input().split()))
  for k in range(len(input_array)):
    if input_array[k] != -1:
      edges.append(Edge(i, k, input_array[k]))

union_find = UnionFind(n)
union_find.init()
edges.sort()

min_cost = 0
mst = []
while len(mst) < n-1:
  edge = edges.pop(0)
  if union_find.same(edge.f, edge.to) == False:
    min_cost += edge.cost
    union_find.union(edge.f, edge.to)
    mst.append(edge)

print(min_cost)

Python: # coding: utf-8
import heapq
n=int(input())
cost=[]
used=[False for i in range(n)]
for i in range(n):
    cost.append(list(map(int,input().split())))
q=[]
heapq.heappush(q,(0,0))
ans=0
while len(q):
    c,newv=heapq.heappop(q)
    if used[newv]:
        continue
    used[newv]=True
    ans+=c
    for nxt in range(n):
        if cost[newv][nxt]!=-1 and not used[nxt]:
            heapq.heappush(q,(cost[newv][nxt],nxt))
print(ans)

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

color = ['White']*n
d = [10**6]*n # 移動コスト
d[0] = 0 # 0にはコストゼロ
p = [-1]*n # 親ノード
p[0] = -1 # 0には親なし

def prim():
    while True:
        mincost = 10**6
        u = -1
        # 最小コストを選ぶ
        for i in range(n):
            if color[i] != 'Black' and d[i] < mincost:
                mincost = d[i]
                u = i

        # 道がない
        if mincost == 10**6:
            break

        color[u] = 'Black'

        # 未訪問かつ道があるならコスト表を更新
        for v in range(n):
            if color[v] != 'Black' and G[u][v] != -1:
                if G[u][v] < d[v]:
                    d[v] = G[u][v]
                    p[v] = u
                    color[v] = 'Gray'
    return d

print(sum(prim()))

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:
            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)
        gravity += minimum

    print(gravity)


main()

Python: import sys
import heapq

def main():
    n = int(input())
    next = []
    for _ in range(n):
        l = list(map(int, input().split()))
        next.append([(c, i) for i, c in enumerate(l) if c != -1])
    visited = [0] * n
    connection = 0
    q = [(0, 0)]    # (cost, v)
    heapq.heapify(q)
    ans = 0
    while len(q):
        cost, v = heapq.heappop(q)
        if visited[v]:
            continue

        # そのノードと繋げる
        visited[v] = 1
        connection += 1
        ans += cost
        
        # 新たに繋げたノードから行けるところをエンキュー
        for i in next[v]:
            heapq.heappush(q, i)
        
        # 全部のノードが繋がったら終了
        if connection == n:
            break
    print(ans)
    return

if __name__ == '__main__':
    main()