Go: package main

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

const R = 100000000

var sc = bufio.NewScanner(os.Stdin)

var n int
var A [101][101]int

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func prim() int {
	var u, Minimum, sum int
	var d, p, color [101]int

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

	for {
		Minimum = R
		u = -1
		for i := 0; i < n; i++ {
			if Minimum > d[i] && color[i] != 2 {
				u = i
				Minimum = d[i]
			}
		}
		if u == -1 {
			break
		}
		color[u] = 2
		for j := 0; j < n; j++ {
			if color[j] != 2 && A[u][j] != R {
				if d[j] > A[u][j] {
					d[j] = A[u][j]
					p[j] = u
					color[j] = 1
				}
			}
		}
	}

	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += A[i][p[i]]
		}
	}
	return sum
}
func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			e := nextInt()
			if e == -1 {
				A[i][j] = R
			} else {
				A[i][j] = e
			}
		}
	}
	fmt.Println(prim())
}

Python: INF = 9999


def prim(M):
    n = len(M)
    color = [0] * n
    d = [INF] * n
    d[0] = 0

    while True:
        minv = INF
        u = -1
        for i in range(n):
            # Black:2
            if minv > d[i] and color[i] != 2:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
    return sum(d)


if __name__ == '__main__':
    n = int(input())
    A = []
    for i in range(n):
        for j in range(n):
            src = input()
            dst = src.replace('-1', 'INF')
            ai = list(map(int, dst.split()))
            A.append(ai)
    print(prim(A))

Python: N = int(input())
color = ["w" for _ in range(N)]
d = [float("inf") for _ in range(N)]
p = [-1 for _ in range(N)]

# Make M
M = [list(map(int, input().split())) for _ in range(N)]

d[0] = 0
while True:
    mincost = float("inf")
    for i in range(N):
        if color[i] != "b" and d[i] < mincost:
            mincost = d[i]
            u = i
    
    if mincost == float("inf"):
        break
    color[u] = "b"

    for v in range(N):
        if color[v] != "b" and M[u][v] != -1:
            if d[v] > M[u][v]:
                d[v] = M[u][v]
                p[v] = u

s = 0 
for i in range(1, N):
    s += M[i][p[i]]
print(s)

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

if __name__ == "__main__":
    main()

Python: import heapq

n = int(input())
edges = [set((w, j) for j, w in enumerate(map(int, input().split())) if w > -1) for _ in range(n)]


def get_minimum():
    global n, edges
    visited = [False] * n
    visited[0] = True
    queue = list(edges[0])
    heapq.heapify(queue)
    total_cost = 0
    while queue:
        cost, vertex = heapq.heappop(queue)
        if visited[vertex]:
            continue
        visited[vertex] = True
        total_cost += cost
        if sum(visited) == n:
            return total_cost
        queue.extend(edges[vertex])
        heapq.heapify(queue)


print(get_minimum())

Python: def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x
    return x
def is_same_set(x,y):
    return root(x) == root(y)
def unite(x,y):
    P[root(x)] = root(y)
    
    

n= int(input())
a=[]
P=[i for i in range(n)]

for i in range(n):
    temp= list(map(int,input().split()))
    for j in range(i,n):
        if temp[j] != -1:
            a.append([temp[j], i, j])
a.sort()
ans=0
for i in a:
    if not(is_same_set(P[i[1]],P[i[2]])):
        unite(i[1],i[2])
        ans+= i[0]
print(ans)

Python: n = int(input())
edgeList = []
rootList = [-1 for i in range(n)]

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(i):
        if a[j] != -1:
            edgeList.append([a[j], getRoot(i), getRoot(j)])
sumLength = 0
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: 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()