Go: package main

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

const R = 100000000

var sc = bufio.NewScanner(os.Stdin)

var n int
var A [101][101]int

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func prim() int {
	var u, Minimum, sum int
	var d, p, color [101]int

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

	for {
		Minimum = R
		u = -1
		for i := 0; i < n; i++ {
			if Minimum > d[i] && color[i] != 2 {
				u = i
				Minimum = d[i]
			}
		}
		if u == -1 {
			break
		}
		color[u] = 2
		for j := 0; j < n; j++ {
			if color[j] != 2 && A[u][j] != R {
				if d[j] > A[u][j] {
					d[j] = A[u][j]
					p[j] = u
					color[j] = 1
				}
			}
		}
	}

	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += A[i][p[i]]
		}
	}
	return sum
}
func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			e := nextInt()
			if e == -1 {
				A[i][j] = R
			} else {
				A[i][j] = e
			}
		}
	}
	fmt.Println(prim())
}

Python: def prim():
    mindist[0] = 0
    parent[0] = -1 

    while True:
        #MSTに追加する頂点を決定
        mincost = INF
        u = -1
        for i in range(n):
            if color[i] != black and mindist[i] < mincost:
                mincost = mindist[i]
                u = i
        if u == -1: break
        color[u] = black
        # MSTに含まれていないMSTとつながる隣接頂点の最小コストを探索
        for v in range(n):
            if color[v] == black: continue
            if M[u][v] == INF: continue
            if M[u][v] >= mindist[v]: continue
            mindist[v] = M[u][v] 
            parent[v] = u
            color[v] = gray
        
    sumcost = 0
    for i in range(n):
        if parent[i] == -1: continue
        sumcost += M[i][parent[i]]

    return sumcost

if __name__ == "__main__":
    n = int(input())
    INF = float("inf")
    M = [list(map(lambda x: INF if x == "-1" else int(x), input().split())) for _ in range(n)]
    white = 0; gray = 1; black =2
    color = [white]*n #各頂点の訪問状態 （white:未訪問 gray:暫定 black:確定）
    mindist = [INF]*n # 各頂点のMSTとつながる辺の最小コスト
    parent = [-1]*n #各頂点の親

    print(prim())

Python: #!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split()) for _ in range(N))) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections
N = int(sys.stdin.readline())
G = tuple(tuple(map(int,sys.stdin.readline().rstrip().split()) for _ in range(N))) # multi line with multi param

INF = float("inf")
W = [INF]*N
A = set(range(N))
T = set()

def add(e):
  T.add(e)
  for i,w in enumerate(G[e]):
    if not i in T and w != -1:
      W[i] = min(W[i],w)
  if not A-T:#W[-1] = -INF
    return -1
  m = min((W[i],i) for i in A-T)
  #print(W,T,m)
  return m[1]

n = add(0)
W[0] = 0
while len(T) < len(G):
  n = add(n)
print(sum(W))

Python: import itertools

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}  # ??¨???????°???¨?????????
weights = []

while V != Vnew:
    T = V - Vnew
    minw = float('inf')
    for u, v in itertools.product(Vnew, T):
        w = A[u][v]
        if w != -1 and minw > w:
            e = (u, v)
            minw = w
    Vnew.add(e[1])
    weights.append(minw)

print(sum(weights))

Python: N = 100

n = int(input())
adj = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    tmp = list(map(int, input().split()))
    u = tmp[0]
    u = u -1
    k = tmp[1]
    v = tmp[2:] -1
    for j in range(k):
        adj[u][v[j]] = 1
        
for i in range(n):
        print(" ".join(list(map(str, adj[i]))))

Python: def root(x):
    path_to_root = []
    while x != P[x]:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node]=x
    return x

def unite(x,y):
    P[root(x)] = root(y)

def is_same_set(x,y):
    return root(x) == root(y)

n = int(input())
P = [i for i in range(n)]
length=[]
points=[]
for i in range(n):
    length.append(list(map(int,input().split())))
for i in range(n):
    for j in range(i,n):
        if length[i][j] != -1:
            points.append((i,j,length[i][j]))
	
points.sort(key=lambda x:x[2])

totalweight = 0
for p in points:
    i,j,w = p
    if not is_same_set(i,j):
       totalweight += w
       unite(i,j)

print(totalweight)

Python: n = int(input())
A = [[int(i) for i in input().strip().split(" ")] for j in range(n)]

dp1={}

for i in range(n):
    for j in range(n):
        if A[i][j] != -1 :
            dp1[(i,j)] = A[i][j]
key = []
value = []
for i,j in sorted(dp1.items(), key=lambda x:x[1]):
    key.append(i)
    value.append(j)

c_v = []
N = len(key)
len_c_v = 0
ans = 0
itr = 0
while itr != N:
    if len_c_v == n:
        break
    i = key[itr][0]
    j = key[itr][1]
    if (i in c_v) == False and (j in c_v) == False:
        c_v.append(i)
        c_v.append(j)
        ans += value[itr]
        len_c_v += 2
        itr += 1
    elif (i in c_v) == False:
        c_v.append(i)
        ans += value[itr]
        itr += 1
        len_c_v += 1
    elif (j in c_v) == False:
        c_v.append(j)
        ans += value[itr]
        itr += 1
        len_c_v += 1
    else:
        itr += 1


if len_c_v != n:
    print(-1)
else:
    print(ans)

Python: n = int(input())
a = []

for i in range(n):
    inp = input()
    if "-1" in inp:
        inp = inp.replace("-1","10000")
    a.append(list(map(int, inp.split())))

w = 0
v = set()
v.add(0)

while len(v) < n:
    min_w   = 10000
    min_idx = 0
    i = 0
    for node in v:
        if min_w > min(a[node]):
            min_w = min(a[node])
            i = node
            min_idx = a[i].index(min_w)
    if min_idx in v:
        a[i][min_idx] = 10000
        continue
    else:
        w += min_w
        v.add(min_idx)

print(w)

Python: import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

class union_find():
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

    def find_root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.find_root(self.root[x])
            return self.root[x]

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

        if x==y:
            return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

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

    def cnt(self,x):
        return -self.root[self.find_root(x)]

n=int(input().rstrip())
G=union_find(n)
g=[]
for k in range(n):
    a=[int(i) for i in input().split()]
    for j in range(n):
        if a[j]!=-1:
            g.append((k,j,a[j]))
g.sort(key=lambda x:x[2])
ans=0
for i in g:
    u,v,c=i
    if not G.same(u,v):
        G.unite(u,v)
        ans+=c
print(ans)