Go: package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	matrix   []int // 隣接行列
	minToMst int   // MSTへの重み最小値
	parent   int   // 最小値の相手
	color    color
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]node, n)
	for i := 0; i < n; i++ {
		nodes[i].matrix = eAtoi((strings.Fields(eGetline(scanner))))
		nodes[i].parent = -1
		nodes[i].minToMst = math.MaxInt16
		nodes[i].color = white
	}

	// 初回はnode[0]がMSTに入るように,minToMstを設定
	nodes[0].minToMst = 0
	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか
		min := math.MaxInt16
		u := -1
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].minToMst < min {
				u = i
				min = nodes[i].minToMst
			}
		}

		if u == -1 {
			break
		}
		// MSTに追加する頂点決定
		nodes[u].color = mst

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みを更新
		for i := 0; i < n; i++ {
			if nodes[i].color == mst {
				continue
			}
			if nodes[i].matrix[u] == -1 {
				// 接してない
				continue
			}
			if nodes[i].matrix[u] < nodes[i].minToMst {
				// node[u]との重みが最小
				nodes[i].minToMst = nodes[i].matrix[u]
				nodes[i].parent = u
			}
		}
	}

	sum := 0
	for _, v := range nodes {
		// node[0]はparentが入っていない
		if v.parent != -1 {
			sum += v.matrix[v.parent]
		}
	}
	fmt.Println(sum)
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

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: M=[]
n=int(input())
for i in range(n):
	b=list(map(int,input().split()))
	M.append(b)
ans=0
from copy import copy
t=[0]
dis=copy(M[0])
dis[0]=10**12
for i in range(n):
	if dis[i]==-1:
		dis[i]=10**10
for i in range(n-1):
	p=10**10
	for j in range(n):
		if dis[j]<p:
			p=dis[j]
			q=j
	ans+=p
	t.append(q)
	dis[q]=10**12
	for j in range(n):
		if dis[j]>M[j][q] and M[j][q]!=-1 and dis[j]!=10**12:
			dis[j]=M[j][q]
print(ans)

Python: from enum import Enum, auto
class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

n = int(input())
M = []
for i in range(n):
    arr = [int(x) for x in input().split(' ') if x != '']
    M.append(arr)
colors = []
d = []
p = [0 for i in range(n)]

INFTY = 2001
def prim():
    global d
    colors = [Color.WHITE for i in range(n)]
    d = [INFTY for i in range(n)]

    d[0] = 0 # iに入る辺の重み **最小全域木は (頂点の数)-1 = (辺の数)
    p[0] = -1 # 0を根にする

    while True:
        mincost = INFTY
        u = 0
        for i in range(n):
            if colors[i] != Color.BLACK and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == INFTY: break

        colors[u] = Color.BLACK
        for v in range(n):
            if colors[v] != Color.BLACK and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    colors[v] = Color.GRAY

prim()
print(sum(d))

Python: def minimum_spanning_tree(adj_mat, cost, color, parent):
    N = len(cost)
    cost[0] = 0
    parent[0] = -1

    while True:
        mincost = 2000000

        for i in range(N):
            if color[i] != "B" and cost[i] < mincost:
                mincost = cost[i]
                cur = i

        if mincost == 2000000:
            break

        color[cur] = "B"

        for v in range(N):
            if color[v] != "B" and adj_mat[cur][v] >= 0:
                if adj_mat[cur][v] < cost[v]:
                    cost[v] = adj_mat[cur][v]
                    parent[v] = cur
                    color[v] = "G"

def Main():
    N = int(input())
    adj_mat = list()
    cost  = [ 2000000 for n in range(N)]
    color = ["W" for n in range(N)]
    parent = [None for n in range(N)]

    for n in range(N):
        adj_mat.append([int(a) for a in input().split()])

    minimum_spanning_tree(adj_mat, cost, color, parent)
    print(sum(cost))

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

Python: n = int(input())

adj = [list(map(int, input().split())) for i in range(n)]


def prim_mst(vn):
    isVisited = [False] * vn
    d = [0] + [2001] * (vn - 1)
    p = [-1] * vn

    while True:
        mincost = 2001
        for i in range(vn):
            if (not isVisited[i]) and (d[i] < mincost):
                mincost = d[i]
                u = i

        if mincost == 2001:
            break

        isVisited[u] = True

        for v in range(vn):
            if (not isVisited[v]) and (adj[u][v] != -1):
                if adj[u][v] < d[v]:
                    d[v] = adj[u][v]
                    p[v] = u

    print(sum(d))


prim_mst(n)

Python: from __future__ import division, print_function
from sys import stdin, maxint
 
 
def main():
    num = int(stdin.readline())
 
    M = []
    for _ in xrange(num):
        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
 
    print(weight)
 
 
main()

Python: import sys
from collections import defaultdict

def push_vertex(vtx: int,queue: list, weights: dict, done: dict):
    queue.extend(weights[vtx])
    done[vtx] = True
    [queue.remove(x) for x in queue[:] if done[x[0]]]
    del weights[vtx]
    queue.sort(key=lambda x: x[1], reverse=True)
    return


def main():
    n = int(input())
    weights = defaultdict(list)
    for i in range(n):
        for idx, weight in enumerate(input().split()):
            if weight != '-1':
                weights[i+1].append((idx+1, int(weight)))
    done = {}
    for i in weights.keys():
        done[i] = False
    mst_weights = 0
    queue = []
    vtx = [*weights][0]
    push_vertex(vtx, queue, weights, done)

    while len(weights) != 0:
        new_vtx, new_vtx_weight = queue.pop()
        mst_weights += new_vtx_weight
        #print(f"connect to {new_vtx} ,weight={new_vtx_weight}")
        push_vertex(new_vtx, queue, weights, done)

    print(mst_weights)
    return

main()