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