Go: package main

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

const (
	MAX   = 100
	INFTY = 1 << 21
	NIL   = -1
)

const (
	WHITE = iota
	GRAY
	BLACK
)

type Graph [MAX][MAX]int

func (g *Graph) prim(n int) int {
	var (
		u, minv     = 0, 0
		d, p, color [MAX]int
	)

	for i := 0; i < n; i++ {
		d[i] = INFTY
		p[i] = -1
		color[i] = WHITE
	}
	d[0] = 0

	for {
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK
		for v := 0; v < n; v++ {
			if color[v] != BLACK && g[u][v] != INFTY {
				if d[v] > g[u][v] {
					d[v] = g[u][v]
					p[v] = u
					color[v] = GRAY
				}
			}
		}
	}

	sum := 0
	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += g[i][p[i]]
		}
	}

	return sum
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	var g Graph
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			sc.Scan()
			e, _ := strconv.Atoi(sc.Text())
			if e == -1 {
				g[i][j] = INFTY
				continue
			}
			g[i][j] = e
		}
	}

	return fmt.Sprint(g.prim(n))
}

func main() {
	fmt.Println(answer(os.Stdin))
}

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():
    n = int(input())
    edges = []

    for i in range(n):
        line = [int(j) for j in input().split()]
        edges += [e for e in line[i + 1:] if e >= 0]

    edges.sort()
    ans = sum(edges[:n - 1])

    print(ans)

if __name__ == '__main__':
    solve()

Python: n=int(input())
edgeList=[]
for i in range(n):
 a=list(map(int,input().split()))
 for j in range(i):
  if a[j]>0:edgeList+=[[a[j],i,j]]
rootList=[-1]*n
sumLength=0
def getRoot(x):
 r=rootList[x]
 if r<0:rootList[x]=x
 elif r!=x:rootList[x]=getRoot(r)
 return rootList[x]
edgeList.sort(key=lambda x:x[0])
for e in edgeList:
 x=getRoot(e[1])
 y=getRoot(e[2])
 if x!=y:
  sumLength+=e[0]
  rootList[x]=rootList[y]=min(x,y)
print(sumLength)

Python: from sys import stdin
INF = 1<<21
WHITE = 0
GRAY = 1
BLACK = 2
n = int(stdin.readline())
M = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(0, n):
    for j, e in enumerate(list(map(int, stdin.readline().split()))):
        if e != -1: M[i][j] = e
d = [INF] * n
d[0] = 0
t = [-1] * n
color = [0] * n
def prim():
    while True:
        minv = INF
        u = -1
        for i in range(0, n):
            if minv > d[i] and color[i] != BLACK:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = BLACK
        for v in range(0, n):
            if color[v] != BLACK and d[v] > M[u][v]:
                d[v] = M[u][v]
                t[v] = u
                color[v] = GRAY
    return sum(d)
print(prim())

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

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

if __name__ == "__main__":
    main()

Python: n=int(input())
m=[list(map(int,input().split()))for _ in[0]*n]
# m = [[-1 for i in range(n)] for j in range(n)]
d=[0]+[10**9]*n
b=[1]*n
a=0
while 1:
  u=-1
  for i in range(n):
    if b[i] and (u<0 or d[i]<d[u]):
      u=i
  if u<0:
    break
  b[u]=0
  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: from __future__ import division, print_function
from sys import stdin, maxint
 
 
def main():
    num = int(stdin.readline())
 
    y = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        y.append([(next(it), next(it)) for _ in xrange(next(it))])
 
    weight = [maxint] * num
    weight[0] = 0
    t = set(xrange(1, num))
    index = 0
 
    while t:
        for v, cost in y[index]:
            if v not in t:
                continue
            weight[v] = min(weight[v], cost + weight[index])

        index = min(t, key=lambda i: weight[i])
        t.remove(index)
 
    for i, d in enumerate(weight):
        print(i, d)
 
 
main()

Python: M=[]
n=int(input())
for i in range(n):
	b=list(map(int,input().split()))
	M.append(b)
ans=0
from copy import copy
t=[0]
dis=copy(M[0])
dis[0]=10**12
for i in range(n):
	if dis[i]==-1:
		dis[i]=10**10
for i in range(n-1):
	p=10**10
	for j in range(n):
		if dis[j]<p:
			p=dis[j]
			q=j
	ans+=p
	t.append(q)
	dis[q]=10**12
	for j in range(n):
		if dis[j]>M[j][q] and M[j][q]!=-1 and dis[j]!=10**12:
			dis[j]=M[j][q]
print(ans)

Python: from enum import Enum, auto
class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

n = int(input())
M = []
for i in range(n):
    arr = [int(x) for x in input().split(' ') if x != '']
    M.append(arr)
colors = []
d = []
p = [0 for i in range(n)]

INFTY = 2001
def prim():
    global d
    colors = [Color.WHITE for i in range(n)]
    d = [INFTY for i in range(n)]

    d[0] = 0 # iに入る辺の重み **最小全域木は (頂点の数)-1 = (辺の数)
    p[0] = -1 # 0を根にする

    while True:
        mincost = INFTY
        u = 0
        for i in range(n):
            if colors[i] != Color.BLACK and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == INFTY: break

        colors[u] = Color.BLACK
        for v in range(n):
            if colors[v] != Color.BLACK and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    colors[v] = Color.GRAY

prim()
print(sum(d))

Python: def minimum_spanning_tree(adj_mat, cost, color, parent):
    N = len(cost)
    cost[0] = 0
    parent[0] = -1

    while True:
        mincost = 2000000

        for i in range(N):
            if color[i] != "B" and cost[i] < mincost:
                mincost = cost[i]
                cur = i

        if mincost == 2000000:
            break

        color[cur] = "B"

        for v in range(N):
            if color[v] != "B" and adj_mat[cur][v] >= 0:
                if adj_mat[cur][v] < cost[v]:
                    cost[v] = adj_mat[cur][v]
                    parent[v] = cur
                    color[v] = "G"

def Main():
    N = int(input())
    adj_mat = list()
    cost  = [ 2000000 for n in range(N)]
    color = ["W" for n in range(N)]
    parent = [None for n in range(N)]

    for n in range(N):
        adj_mat.append([int(a) for a in input().split()])

    minimum_spanning_tree(adj_mat, cost, color, parent)
    print(sum(cost))

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