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: from heapq import heappush, heappop, heapify

n = int(input())
g = [[] for _ in range(n)]

for i in range(n):
    for j,k in enumerate(map(int,input().split())):
        if k != -1:
            g[i].append((j,k))
#    print(g[i])

ocupied = [0]*n
que = [(j,k) for k,j in g[0]] # 重み、子の順番
#print(f'g[0]: {g[0]}')　#子、重みの順番
#print(f'que: {que}')
ocupied[0] = 1
heapify(que)

ans = 0
while que:
    cv,v = heappop(que)
    #print(f'cv, v: {cv}, {v}')
    if ocupied[v]: # vは頂点　どこでvが頂点になるか
        continue
    ocupied[v] = 1
    ans += cv
    for j,k in g[v]:
        if ocupied[j]:
            continue
        heappush(que,(k,j))
    #print(f'ocupied: {ocupied}')
print(ans)

Python: import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

    def same(self, x, y):
        return self.root(self.tree[x]) == self.root(self.tree[y])

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.tree[x] = y


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    uf = UnionFind(N)
    ret = 0
    cost = []
    for i in range(N):
        D = il()
        for j in range(N):
            if D[j] != -1:
                cost.append((D[j], i, j))
    else:
        cost.sort()
        for c, v1, v2 in cost:
            if not uf.same(v1, v2):
                ret += c
                uf.unite(v1, v2)
        print(ret)


if __name__ == '__main__':
    main()

Python: import sys

inf = float('inf')

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def prim(n, As):
    checked = [False] * n
    d = [inf] * n
    checked[0] = True
    d[0] = 0
    nxt = 0
    tot_wgt = 0

    for i in range(n - 1):
        for j in range(n):
            if As[nxt][j] < d[j]:
                d[j] = As[nxt][j]

        min_w = inf
        min_n = 0
        for j in range(n):
            if not checked[j] and min_w > d[j]:
                min_w = d[j]
                min_n = j

        tot_wgt += min_w
        nxt = min_n
        checked[nxt] = True

    return tot_wgt

def solve():
    n = int(input())
    As = []

    for i in range(n):
        line = [int(j) for j in input().split()]
        As.append([i if i != -1 else inf for i in line])

    ans = prim(n, As)

    print(ans)


if __name__ == '__main__':
    solve()

Python: n=int(input())
M=[list(map(int,input().split()))for _ in[0]*n]
d=[0]+[1e4]*~-n
b=[1]*n
a=0
while 1:
 u=-1
 for i in range(n):
  if b[i]and(u<0 or d[i]<d[u]):u=i
 if u<0:break
 b[u]=0
 a+=d[u]
 for v in range(n):
  t=M[u][v]
  if t+1 and d[v]>t:d[v]=t
print(a)

Python: #coding: utf-8

inf = 1000000000
n = int(input())
mtrx = []
for i in range(n):
    col2 = list(map(int,input().split()))
    col = []
    for num in col2:
        if num == -1:
            num = inf
        col.append(num)
    mtrx.append(col)

def prim():
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    p = [None for i in range(n)]
    p[0] = -1
    d[0] = 0

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

        if mincost == inf:
            break

        color[u] = "black"

        for v in range(n):
            if color[v] != "black" and mtrx[u][v] != inf:
                if mtrx[u][v] < d[v]:
                    d[v] = mtrx[u][v]
                    p[v] = u
                    color[v] = "gray"
    print(sum(d))

prim()