Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

const INF = 1 << 60

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	G := make([][]int, N)
	for i := 0; i < N; i++ {
		G[i] = make([]int, N)
		for j := 0; j < N; j++ {
			G[i][j] = sc.nextInt()
		}
	}
	d := make([]int, N)
	for i := 0; i < N; i++ {
		d[i] = INF
	}
	seen := make([]bool, N)
	d[0] = 0
	ans := 0
	for {
		cur := 0
		minCost := INF
		for i := 0; i < N; i++ {
			if !seen[i] && d[i] < minCost {
				minCost = d[i]
				cur = i
			}
		}
		if minCost == INF {
			break
		}
		seen[cur] = true
		ans += d[cur]
		for i := 0; i < N; i++ {
			cost := G[cur][i]
			if cost != -1 && cost < d[i] {
				d[i] = cost
			}
		}
	}

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}

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: # coding: utf-8

n = int(input())
ew = [None] * n
for i in range(n):
    ew[i] = list(map(int, input().split()))

elist = []
for i in range(n):
    for j in range(i+1, n):
        if ew[i][j] > -1:
            elist.append((ew[i][j], i, j))


class UnionFind(object):
    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def find_root(self, i):
        if self.parent[i] != i:
            p = self.parent[i]
            self.parent[i] = self.find_root(p)
        return self.parent[i]

    def same_group(self, i, j):
        return self.find_root(i) == self.find_root(j)

    def union(self, i, j):
        i = self.find_root(i)
        j = self.find_root(j)
        if i != j:
            self.parent[j] = i


uf = UnionFind(n)
esum = 0
for edge in sorted(elist):
    if not uf.same_group(edge[1], edge[2]):
        uf.union(edge[1], edge[2])
        esum += edge[0]

print(esum)

Python: # -*- coding: utf-8 -*-
"""
Created on Sat Apr  6 18:01:32 2019

@author: Yamazaki Kenichi
"""

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
INFTY = 10**6
T = [-1 for i in range(n)]
d = [INFTY for i in range(n)]
p = [0 for i in range(n)]
d[0], p[0] = 0, -1
for j in range(n):
    mincost = 10**6
    for i in range(n):
        if T[i] != 1 and d[i] < mincost:
            mincost = d[i]
            u = i
    T[u] = 1
    for v in range(n):
        if T[v] != 1 and A[u][v] != -1:
            if A[u][v] < d[v]:
                d[v] = A[u][v]
                p[v] = u
                T[v] = 0
print(sum(d))

Python: n = int(input())
edgeArray = [list(map(int, input().split())) for i in range(n)]
edgeList = []
rootList = [-1 for i in range(n)]
sumLength = 0

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        
for i in range(n):
    for j in range(i):
        if edgeArray[i][j] != -1:
            edgeList.append([edgeArray[i][j], i, j])
edgeList.sort(key=lambda x: x[0])
for e in edgeList:
    x = getRoot(e[1])
    y = getRoot(e[2])
    if x != y:
        sumLength += e[0]
        rootList[x] = rootList[y] = min(x, y)
print(sumLength)

Python: import sys
from collections import deque

sys.setrecursionlimit(1000000)
n = int(input())
graph = [[] for _ in range(n)]

global visited 
visited = [0 for _ in range(n)]
global Q, S, T

S = [0] #訪れた順
T = []
visited[0] = 1 #開始位置はすでに訪れたことにする

def input_graph(n):
  for i in range(n):
    vs = list(map(int, input().split()))
    graph[i] = vs
    """for j in range(n):
      if vs[j] != -1:
        tree[i].append([j, vs[j]])"""

def prim():
  global S
  cost = 0
  while len(S) < n:
    max_e = 3000
    ad_v = 0
    ad_list = []
    for s in S:
      for j in range(n):
        if graph[s][j] != -1 and j not in S:
          ad_list.append(graph[s][j])
          #print("s: ",s, " j: ",j, graph[s][j])
          if max_e > graph[s][j]:
            max_e = graph[s][j]
            ad_v = j
    S.append(ad_v)
    cost += max_e
  print(cost)
  

if __name__ == "__main__":
  input_graph(n)
  prim()

Python: import heapq
n = int(input())
ans = 0
cost = []
for i in range(n):
    L = list(map(int,input().split()))
    cost.append(L)
used = [False]*n
used[0] = True #島0から探索を始める。
edge = []
for i in range(n):
    T = []
    edge.append(T)
for i in range(n):
    for j in range(n):
        if cost[i][j] != -1:
            edge[i].append([cost[i][j],j])
P = edge[0]
P.sort()
while len(P) != 0:
    cur = heapq.heappop(P)
    d = cur[0]
    next = cur[1]
    if used[next] == True:
        continue
    used[next] = True
    ans += d
    for e in edge[next]:
        heapq.heappush(P,[e[0],e[1]])
print(ans)

Python: import heapq


class MinimumSpanningTree:
    """ Prim's algorithm: find minimum spanning tree
        Complexity: O(E log(V))
        used in GRL2A(AOJ)
    """

    def __init__(self, V, E, start=0, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (undirected graph)
            start: start vertex
            INF: Infinity cost
        """
        self.prim(V, E, start, INF)

    def prim(self, V, E, start=0, INF=10**9):
        used = [False] * V
        self.mincost = 0
        que = []
        heapq.heappush(que, (0, 0))
        while len(que) > 0:
            cost, v = heapq.heappop(que)
            if used[v]:
                continue
            used[v] = True
            self.mincost += cost
            for to, c in E[v]:
                heapq.heappush(que, (c, to))

    def minCost(self):
        return self.mincost

V = int(input())
edge = [[] for _ in range(V)]
for i in range(V):
    for j, d in enumerate(map(int, input().split())):
        if d != -1:
            edge[i].append((j, d))
mst = MinimumSpanningTree(V, edge)
print(mst.minCost())