Go: package main

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

const (
	MAX   = 100
	INFTY = 1 << 21
	NIL   = -1
)

const (
	WHITE = iota
	GRAY
	BLACK
)

type Graph [MAX][MAX]int

func (g *Graph) prim(n int) int {
	var (
		u, minv     = 0, 0
		d, p, color [MAX]int
	)

	for i := 0; i < n; i++ {
		d[i] = INFTY
		p[i] = -1
		color[i] = WHITE
	}
	d[0] = 0

	for {
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK
		for v := 0; v < n; v++ {
			if color[v] != BLACK && g[u][v] != INFTY {
				if d[v] > g[u][v] {
					d[v] = g[u][v]
					p[v] = u
					color[v] = GRAY
				}
			}
		}
	}

	sum := 0
	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += g[i][p[i]]
		}
	}

	return sum
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	var g Graph
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			sc.Scan()
			e, _ := strconv.Atoi(sc.Text())
			if e == -1 {
				g[i][j] = INFTY
				continue
			}
			g[i][j] = e
		}
	}

	return fmt.Sprint(g.prim(n))
}

func main() {
	fmt.Println(answer(os.Stdin))
}

Python: from heapq import heappush, heappop, heapify

N = int(input())
edges = [[] for i in range(N)]
for v in range(N):
    for w, c in enumerate(map(int, input().split())):
        if c != -1:
            edges[v].append((w, c))

visited = [0]*N
que = [(c, w) for w, c in edges[0]]
visited[0] = 1
heapify(que)

d=[0]+[10**9]*(N-1)

#左がコスト
ans = 0
while que:
    c, u = heappop(que)
    if visited[u]:
        continue
    visited[u] = 1
    d[u]=c
    for v, c in edges[u]:
        if visited[v]:
          continue
        heappush(que, (c, v))
print(sum(d))

Python: graph_n=int(input())


edge_dict={}



for i in range(graph_n):
    tmp_row=list(map(int,input()))
    for j in range(graph_n):
        if(tmp_row[j]!=-1):
            try:
                edge_dict[tmp_row].append([i,j])
            except:
                edge_dict[tmp_row]=[[i,j]]

sorted_edge=sorted(edge_dict.items())
vertex_flag=[0]*graph_n

searched_vertex_num=0
cost=0

for edges in sorted_edge:
    for edge in edges[1]:
        if(vertex_flag[edge[0]]==0 and vertex_flag[edge[1]]==0):
            vertex_flag[edge[0]]=1
            vertex_flag[edge[1]]=1
            seached_vertex_num+=2
            cost+=edges[0]
            if(graph_n <=searched_vertex_num):
                break

        elif(vertex_flag[edge[0]]==0 and vertex_flag[edge[1]]==1):
            vertex_flag[edge[0]]=1
            vertex_flag[edge[1]]=1
            seached_vertex_num+=1
            cost+=edges[0]
            if(graph_n <=searched_vertex_num):
                break

        elif(vertex_flag[edge[0]]==1 and vertex_flag[edge[1]]==0):
            vertex_flag[edge[0]]=1
            vertex_flag[edge[1]]=1
            seached_vertex_num+=1
            cost+=edges[0]
            if(graph_n <=searched_vertex_num):
                break

    if(graph_n <=searched_vertex_num):
        break


print(cost)

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