Go: package main

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

// Define disjoint-set forests

type vertexNo int

type vertex struct {
	number vertexNo
	rank int
	parent *vertex
}

func makeSet(number vertexNo) vertex {
	return vertex {
		number: number,
		rank: 0,
		parent: nil,
	}
}

func union(x, y *vertex) *vertex {
	return link(findSet(x), findSet(y))
}

func link(x, y *vertex) *vertex {
	if x.rank > y.rank {
		y.parent = x
		return x
	} else {
		x.parent = y
		if x.rank == y.rank {
			y.rank += 1
		}
		return y
	}
}

func findSet(v *vertex) *vertex {
	if v.parent == nil {
		return v
	}
	v.parent = findSet(v.parent)
	return v.parent
}

// Function to calculate minimum spanning tree

type matrix [][]int

type edge struct {
	one vertexNo
	two vertexNo
	weight int
}

const(
	MAX_VERTICES = 100
)

func newEdgesFromMatrix(matrix matrix) []edge {
	edges := make([]edge, 0, MAX_VERTICES * MAX_VERTICES)

	for i := 0; i < len(matrix); i++ {
		row := matrix[i]
		for j := i; j < len(row); j++ {
			if row[j] >= 0 {
				edge := edge{one: vertexNo(i+1), two: vertexNo(j+1), weight: row[j]}
				edges = append(edges, edge)
			}
		}
	}

	return edges
}

func solve(matrix matrix) int {
	nVertices := len(matrix)

	// initialize vertices
	vertices := make([]vertex, nVertices)
	for i := 0; i < nVertices; i++ {
		vertices[i] = makeSet(vertexNo(i+1))
	}

	// prepare edges sorted in the ascending order of weight
	edges := newEdgesFromMatrix(matrix)
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})

	unionCount := 0
	weightSum := 0
	for unionCount < nVertices-1 {
		for i := 0; i < len(edges); i++ {
			edge := edges[i]
			v1 := &vertices[edge.one-1]
			v2 := &vertices[edge.two-1]
			rep1 := findSet(v1)
			rep2 := findSet(v2)
			if rep1.number == rep2.number {
				continue
			}
			union(rep1, rep2)
			edges = append(edges[0:i], edges[i+1:]...)
			weightSum += edge.weight
			unionCount++
			break
		}
	}

	return weightSum
}

// main

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	matrix := parseMatrix(n, sc)

	edges := newEdgesFromMatrix(matrix)
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].weight < edges[j].weight
	})

	fmt.Println(solve(matrix))
}

func parseMatrix(n int, sc *bufio.Scanner) [][]int {
	matrix := make([][]int, n)
	for i := 0; i < n; i++ {
		matrix[i] = make([]int, n)
		for j := 0; j < n; j++ {
			x, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			matrix[i][j] = x
		}
	}
	return matrix
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextInt(sc *bufio.Scanner) (int, error) {
	return strconv.Atoi(nextText(sc))
}

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

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