Go: package main

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

const (
	MAX_N      = 200
	MAX_WEIGHT = 2000
)

type Edge struct {
	start  int
	end    int
	weight int
}

type ShortestInfo struct {
	edges    []Edge
	shortest int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	shortestList := make([]ShortestInfo, n)
	for i := 1; i < n; i++ {
		shortestList[i] = ShortestInfo{edges: []Edge{}, shortest: MAX_N*MAX_WEIGHT + 1}
	}

	adjacentMatrix := make([][]int, n)
	for i := 0; i < n; i++ {
		adjacentMatrix[i] = make([]int, n)
		for j := 0; j < n; j++ {
			v, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			adjacentMatrix[i][j] = v
		}
	}

	mst([]int{1}, shortestList, adjacentMatrix)
	fmt.Println(calculateMinWeight(shortestList))
}

func calculateMinWeight(shortestList []ShortestInfo) int {
	visitedList := make([]bool, len(shortestList))
	visitedList[0] = true
	sumWeight := 0
	for !visitedAll(visitedList) {
		shortestInfo := shortestList[0]
		shortestList = shortestList[1:]
		edges := shortestInfo.edges
		for _, edge := range edges {
			if !visitedList[edge.end-1] {
				visitedList[edge.end-1] = true
				sumWeight += edge.weight
			}
		}
	}
	return sumWeight
}

func visitedAll(visitedList []bool) bool {
	for _, v := range visitedList {
		if !v {
			return false
		}
	}
	return true
}

func mst(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]int) {
	for len(nodeStack) > 0 {
		currentNode := nodeStack[0]
		nodeStack = nodeStack[1:]
		currentShortest := getShortest(currentNode, shortestList)
		adjacents := findAdjacents(currentNode, adjacentMatrix)
		for i := 0; i < len(adjacents); i++ {
			adj := adjacents[i]
			s := getShortest(adj.end, shortestList)
			if currentShortest.shortest+adj.weight < s.shortest || (currentShortest.shortest+adj.weight == s.shortest && len(currentShortest.edges)+1 > len(s.edges)) {
				setShortest(adj.end, adj, currentShortest, shortestList)
				nodeStack = append(nodeStack, adj.end)
			}
		}
	}
}

func getShortest(node int, shortestList []ShortestInfo) ShortestInfo {
	return shortestList[node-1]
}

func setShortest(node int, edge Edge, currentShortest ShortestInfo, shortestList []ShortestInfo) {
	newEdges := make([]Edge, len(currentShortest.edges)+1)
	for i := 0; i < len(newEdges)-1; i++ {
		newEdges[i] = currentShortest.edges[i]
	}
	newEdges[len(newEdges)-1] = edge
	shortestInfo := ShortestInfo{edges: newEdges, shortest: currentShortest.shortest + edge.weight}
	shortestList[node-1] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]int) []Edge {
	adjacents := adjacentMatrix[currentNode-1]
	edges := []Edge{}
	for i, v := range adjacents {
		if v > 0 {
			edges = append(edges, Edge{start: currentNode, end: i + 1, weight: v})
		}
	}
	return edges
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

Python: # -*- coding: utf-8 -*-
'''
所要時間は、分位であった。
'''
# ライブラリのインポート
#import re #正規表現
import sys
#import heapq
import bisect
#import collections
#import math

def main():
    n = int(input())
    X = [[] for i in range(n)]
    l = []
    for i, line in enumerate(sys.stdin):
        X[i] = list(line.strip("\n").split())
        for j in range(i,n):
            c = int(X[i][j])
            if c == -1:
                continue
            else:
                r = (c,i,j)
                bisect.insort(l, r)
    
    uf = UnionFind(n)
    k = 0
    ans = 0
    count = 0
    while(count < n):
        try: tmp = l[k]
        except: break
        x = tmp[1]
        y = tmp[2]
        if not uf.same(x,y):
            uf.unite(x, y)
            ans += tmp[0] 
            count += 0
        k += 1
    print(ans)

class UnionFind:
    def __init__(self,n):
        self.p = [i for i in range(n)]
        return
    
    def root(self,x):
        while(1):
            if (self.p[x] == x): break
            y = x
            x = self.p[x]
            self.p[y] = self.p[x]
        return x

    def unite(self ,x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: return
        else:
            self.p[rx] = ry
            return 
    
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry


    
if __name__ == '__main__':
    main()

Python: # -*- coding: utf-8 -*-
"""
Created on Sat Sep 22 11:44:37 2018
ALDS1-12-A
@author: maezawa
"""
import heapq

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

adj = [[] for _ in range(n+1)]
for i in range(n):
    for j in range(i, n):
        if amat[i][j] == -1:
            continue
        adj[i+1].append([amat[i][j], j+1])
        adj[j+1].append([amat[j][i], i+1])

#print(adj)
d = [10**10]*(n+1)
h = []
heapq.heappush(h, [0, 1]) # [cost, node]
visited = [False]*(n+1)
while h:
    cost, node = heapq.heappop(h)
    if visited[node] == False and cost < d[node]:
        d[node] = cost
        visited[node] = True
        for nextnode in adj[node]:
            if visited[nextnode[1]]:
                continue
            heapq.heappush(h,nextnode)

d.pop(0)
print(sum(d))

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
        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: n=int(input())
m = [[-1 for i in range(n)] for j in range(n)]
for i in range(n): #隣接の辺のコストを入力
  nums = list(map(int, input().split()))
  for j in range(n):
    m[i][j] = nums[j]

d=[0]+[10**9]*n
visited=[0]*n
a=0
while 1:
  u=-1
  for i in range(n):
    if not visited[i] and (u<0 or d[i]<d[u]):
      u=i
  if u<0:
    break
  visited[u]=1
  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: n = int(input())
A = []
for i in range(n):
    line = input()
    A.append([int(x) for x in line.split()])

V = set(range(n))
Vnew = {0}  # ??¨???????°???¨?????????
weight = 0

while V != Vnew:
    T = V - Vnew
    minw = float('inf')
    for u in Vnew:
        for v in T:
            w = A[u][v]
            if w != -1:
                e = (u, v)
                minw = min(minw, w)
    Vnew.add(e[1])
    weight += minw


print(weight)

Python: import sys
input = sys.stdin.readline
INF = 100100

def prim(n: int, M: list):
    ans = 0
    visited = [False] * n
    d = [INF] * n
    p = [-1] * n
    d[0] = 0
    while True:
        mincost = INF
        for i in range(n):
            if not visited[i] and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == INF:
            break
        ans += mincost
        visited[u] = True
        for v in range(n):
            if not visited[v] and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
    return ans

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

if __name__ == '__main__': main()