Go: package main

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

const (
	MAX = 100
	INF = 1 << 21
	WHITE = 0
	GRAY = 1
	BLACK = 2
)

var (
	n int
	M [MAX][MAX]int
)

func prim() int {
	var u, minv int
	var d [MAX]int
	var p [MAX]int
	var color [MAX]int

	for i := 0; i < n; i++ {
		d[i] = INF
		p[i] = -1
		color[i] = WHITE
	}
	d[0] = 0
	for {
		minv = INF
		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 && M[u][v] != INF {
				if d[v] > M[u][v] {
					d[v] = M[u][v]
					p[v] = u
					color[v] = GRAY
				}
			}
		}
	}
	sum := 0
	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += M[i][p[i]]
		}
	}
	return sum
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Scan()
	n, _ = strconv.Atoi(scanner.Text())
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			scanner.Scan()
			e, _ := strconv.Atoi(scanner.Text())
			if e == -1 {
				M[i][j] = INF
			} else {
				M[i][j] = e
			}
		}
	}
	fmt.Println(prim())
}

Python: import sys
from operator import add

n = int(sys.stdin.readline().strip())
A = [ [0] for i in range(n)]
for i in range(n):
	temp = map(int ,sys.stdin.readline().strip().split(" "))
	A[i] = temp


weight = [None for i in range(n)]
mitayatu=[False for i in range(n)]

def min(array):
	temp = 100000
	index= 0
	for i in range(n):
		if array[i] is not None and mitayatu[i]==False:
			if temp>=array[i]:
				temp = array[i]
				index = i
	return index

def owari():
	for i in mitayatu:
		if i is False:
			return False
	return True
# zero origin
def prim(nodeid):
	#print(nodeid)
	if owari() == True:
		return
	if mitayatu[nodeid]==True:
		return
	mitayatu[nodeid]=True
	for i in range(n):
		if A[nodeid][i]!=-1:
			if weight[i] is None:
				weight[i]=A[nodeid][i]
			elif weight[i]>A[nodeid][i] and mitayatu[i]==False:
				weight[i]=A[nodeid][i]
	prim(min(weight))

weight[0]=0
prim(0)

#print(weight)
print(reduce(add, weight))

Python: INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2
d = [INFTY for i in range(n)]
p = [-1 for i in range(n)]
color = [WHITE for i in range(n)]

n = int(input())
M = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
    for j in range(n):
        if (M[i][j] == -1):
            M[i][j] = INFTY

def prim():
    global M, d, p, color
    d[0] = 0
    while(1):
        minv = INFTY
        u = -1
        for i in range(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(n):
            if (color[v] != BLACK and M[u][v] != INFTY):
                if (d[v] > M[u][v]):
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY
    
    return sum([M[i][p[i]] for i in range(n) if p[i] != -1])

print(prim())

Python: # -*- coding: utf-8 -*-
from heapq import heappop, heappush


def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):
    '''
    Returns the Minimum Spanning Tree(MST) of a given graph

    # sample input when given not as adjacency list (adj_matrix=False) (generally works faster)
    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0
             [(0, 2), (3, 3), (4, 6)],         # node 1
             [(0, 5), (3, 2), (5, 6)],         # node 2
             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3
             [(1, 6), (3, 2), (5, 4)],         # node 4
             [(2, 6), (4, 4)]]                 # node 5

    # sample input when given as adjacency matrix (adj_matrix=True)
    edges = [[0, 2, 5, 4, inf, inf],           # node 0
             [2, 0, inf, 3, 6, inf],           # node 1
             [5, inf, 0, 2, inf, 6],           # node 2
             [4, 3, 2, 0, 2, inf],             # node 3
             [inf, 6, inf, 2, 0, 4],           # node 4
             [inf, inf, 6, inf, 4, 0]]         # node 5
    '''

    n = len(edges)

    prevs = [-1] * n
    costs = [float('inf')] * n
    costs[start] = 0
    pq = [(0, start)]
    T = [True] * n
    rem = n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        T[tmp_node] = False
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value and T[node]) if adj_matrix else\
                    ((node, cost) for node, cost in edges[tmp_node] if T[node])

        for nxt_node, nxt_cost in nxt_edges:
            if costs[nxt_node] > nxt_cost:
                costs[nxt_node] = nxt_cost
                prevs[nxt_node] = tmp_node
                heappush(pq, (nxt_cost, nxt_node))
                T[nxt_node] = True

    else:
        if len([prev for prev in prevs if prev != -1]) != n - 1:
            raise NoSpanningError(
                'There is no spanning tree in this graph (search started from node{})'.
                format(start))

        else:
            return prevs, costs


class NoSpanningError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_A
    '''

    n = int(input())
    edges = [[(j, int(cost)) for j, cost in enumerate(input().split())
              if int(cost) != -1] for i in range(n)]

    prevs, costs = prim(edges)
    print(sum(costs))

Python: def prim(cost):
    sumcost = 0
    V = len(cost)
    mincost = [float('inf')] * V
    used = [False] * V
    mincost[0] = 0
    while True:
        j = -1
        for i in range(V):
            if not used[i] and (j == -1 or mincost[i] < mincost[j]):
                j = i
        if j == -1:
            break
        used[j] = True
        sumcost = sumcost + mincost[j]
        for i in range(V):
            if cost[i][j] == -1:
                continue
            mincost[i] = min(mincost[i], cost[j][i])
    return sumcost

Python: n = int(input())
T = [i for i in range(n)]
def root(x):
    path_to_root = []
    while T[x] != x:
        path_to_root.append(x)
        x = T[x]
    for node in path_to_root:
        T[node] = x
    return x
def is_same_set(x,y):
    return root(x) == root(y)
def unite(x,y):
    T[root(x)] = root(y)

A = []
W = []
for i in range(n):
    A.append(list(map(int,input().strip().split(' '))))
    for j in range(i+1,n):
        if A[i][j] != -1:
            W.append([A[i][j],i,j])
W.sort()
sum = 0
for i in range(len(W)):
    if not is_same_set(W[i][1],W[i][2]):
        unite(W[i][1],W[i][2])
        sum += W[i][0]
print(sum)

Python: import heapq

n = int(input())
A = [[int(i) for i in input().split()] for i in range(n)]
h = []
DP = {}
heapq.heappush(h,(0,0))
c = 0
while(len(DP)<n):
    tmp = heapq.heappop(h)
    c += tmp[0]
    DP[tmp[1]] = 1
    for i,j in enumerate(A[tmp[1]]):
        if j > 0 and not i in DP:
            heapq.heappush(h,(j,i))
print(c)

Python: def kruskal(n):
    cost = []
    t = set()
    while edge:
        cmin = min(weight)
        index = weight.index(cmin)
        e = edge[index]
        del weight[index]
        del edge[index]
        if not e <= t:
            cost.append(cmin)
            t |= e
    return sum(cost)

n = int(input())
edge = []
weight = []
for i in range(n):
    for j, c in enumerate(map(int, input().split())):
        if c != -1 and not {i, j} in weight:
            edge.append({i, j})
            weight.append(c)
print(kruskal(n))

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)