Go: package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	I int
	J int
	A int
}

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]int, n)
	edges := make([]Edge, 0, n*(n-1)/2)
	parents := make([]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			fmt.Scan(&g[i][j])
			if g[i][j] >= 0 {
				edges = append(edges, Edge{i, j, g[i][j]})
			}
		}
		parents[i] = i
	}
	sort.SliceStable(edges, func(i, j int) bool { return edges[i].A >= edges[j].A })

	sum := 0
	num := 0
	for len(edges) > 0 && num < n-1 {
		edge := edges[len(edges)-1]
		edges = edges[:len(edges)-1]

		if same(edge.I, edge.J, &parents) {
			continue
		}
		union(edge.I, edge.J, &parents)
		sum += edge.A
		num += 1
	}
	fmt.Println(sum)
}



func root(id int, parents *[]int) int {
	if id == (*parents)[id] {
		return id
	}
	return root((*parents)[id], parents)
}

func union(i, j int, parents *[]int) {
	(*parents)[root(j, parents)] = (*parents)[root(i, parents)]
}

func same(i, j int, parents *[]int) bool {
	return root(i, parents) == root(j, parents)
}

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