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: import sys

n = int(sys.stdin.readline())
g = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

V = set(range(n))
U = set()
E = []

U.add(V.pop())

while len(U)<n:
    minw = 1e10
    mine = []
    for u in U:
        for v in V:
            if g[u][v]>=0 and minw>g[u][v]:
                minw = g[u][v]
                mine = [u, v]
    E.append(mine)
    U.add(mine[1])
    V.remove(mine[1])

vv=0
for u, v in E:
    vv += g[u][v]
print(vv)

Python: def prim(n, cost):
    mincost = [float("inf")]*n
    used = [False] * n
    mincost[0] = 0
    res = 0
    cnt = 1
    while True:
        u = -1
        for i in range(n):
            if (not used[i]) and (u == -1 or mincost[i] < mincost[u]):
                u = i
        if u == -1:
            break
        used[u] = True
        res += mincost[u]
        for v in range(n):
            if cost[u][v] != -1:
                mincost[v] = min(mincost[v], cost[u][v])
    return res


def main():
    n = int(input())
    g = []
    for _ in range(n):
        g.append(list(map(int, input().split())))
    print(prim(n, g))



if __name__ == '__main__':
    main()

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

for i in range(n):
  for index, j in enumerate(list(map(int, input().split()))):
    edges[i][index] = j

inf = 9999999999999999
distances = [inf] * n
colors = ["white"] * n

def mst(u):
  distances[u] = 0
  colors[u] = "gray"

  while True:
    mincost = inf
    for i in range(n):
      if colors[i] != "black" and distances[i] < mincost:
        mincost = distances[i]
        u = i

    if mincost == inf:
      break

    colors[u] = "black"

    for index, weight in enumerate(edges[u]):
      if weight != -1 and colors[index] != "black" and distances[index] > weight:
        distances[index] = weight
        colors[index] = "gray"

mst(0)
print(sum(distances))

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: from __future__ import division, print_function
from sys import stdin, maxint
 
 
def main():
    x = int(stdin.readline())
 
    y = []
    for _ in xrange(x):
        y.append([int(s) for s in stdin.readline().split()])
 
    g = set(xrange(1, x+1))
    index = g.pop()
    h = {index}
    leng = 0
 
    while g:
        minimum = maxint

        for j in h:
            mj = y[j-1]
            for i in g:
                if 0 <= mj[i-1] < minimum:
                    index = i
                    minimum = mj[i-1]

        h.add(index)
        g.remove(index)
        leng += minimum
 
    print(leng)
 
 
main()

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


def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):
    n = len(edges)

    costs = [float('inf')] * n
    costs[start] = 0
    prevs = [-1] * n

    pq = [(0, start)]
    T = [True] * n

    while pq:
        tmp_cost, tmp_node = heappop(pq)
        T[tmp_node] = False

        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__':
    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))