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] }

// Main
type Node struct {
	cost int
	done bool
}

type Edge struct {
	to, cost int
}

const INF = 1 << 60

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	nodes := make([]Node, N)
	for i := 0; i < N; i++ {
		nodes[i].cost = INF
	}
	E := make([][]Edge, N)
	for i := 0; i < N; i++ {
		id, k := sc.nextInt(), sc.nextInt()
		for j := 0; j < k; j++ {
			to, cost := sc.nextInt(), sc.nextInt()
			E[id] = append(E[id], Edge{to, cost})
		}
	}
	nodes[0].cost = 0
	for {
		cur := 0
		minCost := INF
		for i := 0; i < N; i++ {
			n := nodes[i]
			if !n.done && n.cost < minCost {
				cur = i
				minCost = n.cost
			}
		}
		if minCost == INF {
			break
		}
		nodes[cur].done = true
		for i := 0; i < len(E[cur]); i++ {
			to, cost := E[cur][i].to, E[cur][i].cost+nodes[cur].cost
			if !nodes[to].done && cost < nodes[to].cost {
				nodes[to].cost = cost
			}
		}
	}

	for i := 0; i < N; i++ {
		fmt.Fprintln(wtr, i, nodes[i].cost)
	}
	wtr.Flush()
}

Python: """Shortest Path"""

import sys
import os
import pprint

#fd = os.open('ALDS1_12_B.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

level = True
def debug(v):
    if level:
        print(v)

n = int(input())
INF = 100001
W = [[INF for j in range(n)] for i in range(n)]

for _ in range(n):
    l = list(map(int, input().split()))
    node_index = l[0]
    num = l[1]
    data = l[2:]
    for i in range(num):
        node = data[i*2]
        weight = data[i*2+1]
        W[node_index][node] = weight

d = [INF] * n
visited = [False] * n
parent = [None] * n

# root
d[0] = 0

while True:
    min_dist = INF
    min_index = None
    for i in range(n):
        if not visited[i] and d[i] < min_dist:
            min_dist = d[i]
            min_index = i

    if min_index is None:
        break

    # accept
    visited[min_index] = True

    for i in range(n):
        if not visited[i] and d[i] > d[min_index] + W[min_index][i]:
            d[i] = d[min_index] + W[min_index][i]
            parent[i] = min_index
for i in range(len(d)):
    s = '{} {}'.format(i, d[i])
    print(s)

Python: import heapq

n = int(input())
edges = [None] * n
for _ in range(n):
    l = list(map(int, input().split()))
    edges[l[0]] = set((c, j) for j, c in (l[i:i + 2] for i in range(2, l[1] * 2 + 2, 2)))

min_costs = [0] * n
visited = [False] * n
visited[0] = True
queue = list(edges[0])
heapq.heapify(queue)

while queue:
    total_cost, vertex = heapq.heappop(queue)
    if visited[vertex]:
        continue
    visited[vertex] = True
    min_costs[vertex] = total_cost
    for cost, vertex2 in edges[vertex]:
        if not visited[vertex2]:
            heapq.heappush(queue, (total_cost + cost, vertex2))

for r in enumerate(min_costs):
    print(*r)

Python: n = int(input())

INF = 2147483647
M = [[INF for j in range(n)] for i in range(n)]
check, dist = [0 for i in range(n)], [INF for i in range(n)]


def dijkstra(s):
    p = [-1 for i in range(n)]
    dist[s] = 0

    while True:
        min_cost = INF
        for i in range(n):
            if check[i] != 2 and dist[i] < min_cost:
                min_cost = dist[i]
                u = i

        if min_cost == INF:
            break

        check[u] = 2

        for v in range(n):
            if check[v] != 2 and M[u][v] != INF:
                if dist[u] + M[u][v] < dist[v]:
                    dist[v], p[v] = dist[u] + M[u][v], u
                    check[v] = 1


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(data[1]):
            M[data[0]][data[2*(j+1)]] = data[2*(j+1)+1]

    dijkstra(0)

    for i in range(n):
        print(i, dist[i])


if __name__ == '__main__':
    main()

Python: def createMatrix():
    matrix = [[INFTY] * n for i in range(n)]
    for i in range(n):
        u, k, *v = map(int, input().split())
        for j in range(0, k*2, 2):
            matrix[i][v[j]] = v[j+1]
    return matrix

def dijkstra():
    d[0] = 0
    p[0] = -1

    while True:
        mincost = INFTY
        # cost が最小の node を選択
        for i in range(n):
            if status[i] != VISITED and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INFTY:
            break

        status[u] = VISITED

        # u と v をつなぐ edge のうち最小の経路のコストの合計に更新
        for v in range(n):
            if status[v] != VISITED and matrix[u][v] != INFTY:
                if d[u] + matrix[u][v] < d[v]:
                    d[v] = d[u] + matrix[u][v]
                    p[v] = u
                    status[v] = VISITING

import sys
# sys.stdin = open('input.txt')

n = int(input())
NOT_VISITED = 0 # WHITE
VISITING = 1 # GRAY
VISITED = 2 # BLACK
INFTY = 10**21

matrix = createMatrix()
status =  [NOT_VISITED] * n
d = [INFTY] * n
p = [-1] * n

dijkstra()

for i in range(n):
    print(i, d[i])