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: def kruskal(edges):
    edges.sort(key=lambda pair:pair[2])
    uf_tree = UnionFindTree(n_node)
    total_cost = 0
    for i, j, cost in edges:
        if cost < 0:
            continue

        if not uf_tree.have_same_root(i, j):
            uf_tree.unite(i, j)
            total_cost += cost
    return total_cost


class UnionFindTree:
    def __init__(self, n_node):
        self.parent = [i for i in range(n_node)]
        self.rank = [0] * n_node

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
            else:
                self.parent[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def have_same_root(self, x, y):
        return self.find(x) == self.find(y)

if __name__ == "__main__":
    n_node = int((input()))
    edges = []
    for i in range(n_node):
        for j, cost in enumerate(map(int, input().split())):
            edges.append((i, j, cost))

    print(kruskal(edges))

Python: class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


class Kruskal:
    """ Kruskal's algorithm: find minimum spanning tree
        Complexity: O(E log(V))
        used in GRL2A(AOJ)
    """

    def __init__(self, V, E, start=0, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (undirected graph)
        """
        self.kruskal(V, E)

    def kruskal(self, V, E):
        edges = []
        for v1 in range(V):
            for v2, cost in E[v1]:
                if v1 < v2:
                    edges.append((cost, v1, v2))
        edges.sort(reverse=True)
        self.mincost = 0
        self.minSpanningTree = []
        uf = UnionFindTree(V)
        while len(self.minSpanningTree) < V-1:
            cost, v1, v2 = edges.pop()
            if uf.same(v1, v2) == False:
                self.mincost += cost
                uf.unite(v1, v2)
                self.minSpanningTree.append((v1, v2, cost))

    def minCost(self):
        return self.mincost

    def getMinSpanningTree(self):
        return sorted(self.minSpanningTree)

V = int(input())
edge = [[] for _ in range(V)]
for i in range(V):
    for j, d in enumerate(map(int, input().split())):
        if d != -1:
            edge[i].append((j, d))
mst = Kruskal(V, edge)
print(mst.minCost())

Python: from sys import stdin
INF = 1<<21
WHITE, GRAY, BLACK = 0, 1, 2
n = int(stdin.readline())
M = [[INF] * n for _ in range(n)]
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
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]
    return sum(d)
print(prim())

Python: # -*- coding: utf_8 -*-
level = False
def debug(v):
    if level:
        print(v)

n = int(input())
g = []

for i in range(n):
    v = input().split()
    g.append([int(x) for x in v]) 

debug(g)

def prim(n):
    visited = [False] * n
    d = [0] + [2001] * (n - 1)
    p = [-1] * n

    while True:
        mincost = 2001

        for i in range(n):
            if (not visited[i]) and (d[i] < mincost):
                mincost = d[i]
                u = i
        if mincost == 2001:
            break
        visited[u] = True

        for v in range(n):
            if (not visited[v]) and (g[u][v] != -1):
                if g[u][v] < d[v]:
                    d[v] = g[u][v]
                    p[v] = u

    print(sum(d))

prim(n)