Go: package main

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

const BIG_COST = 200000

type Path struct {
	node int
	cost int
}

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

	nNodes := scanInt(sc)

	// 各頂点につながる頂点一覧を得るための隣接リスト
	graph := make([][]Path, nNodes)

	for i := 0; i < nNodes; i++ {
		u := scanInt(sc)
		k := scanInt(sc)
		graph[i] = make([]Path, k)
		for d := 0; d < k; d++ {
			graph[u][d] = Path{
				node: scanInt(sc),
				cost: scanInt(sc),
			}
		}
	}

	// 0 から各頂点への最小コストを保存する配列
	minCosts := make([]int, nNodes)

	minCosts[0] = 0
	for i := 1; i < nNodes; i++ {
		minCosts[i] = BIG_COST
	}

	// 各頂点が調査済みかどうかを保持する配列
	checked := make([]bool, nNodes)

	// 最小コストのパスを高速に取得するためのヒープ。
	// コストが小さいものほどルートに来るようにする。
	heap := NewHeap(func(a, b Path) bool {
		return a.cost < b.cost
	})

	heap.insert(Path{node: 0, cost: 0})
	for heap.size > 0 {
		u := heap.extractMax()

		// 隣接行列を使っていた時とは違い、ヒープには
		// 同じノードへのパスが複数含まれうる。そのため既によりコストの低い
		// パスが見つかっている場合は無視する。
		if minCosts[u.node] < u.cost {
			continue
		}

		checked[u.node] = true

		for _, v := range graph[u.node] {
			cost := v.cost + u.cost
			if !checked[v.node] && cost < minCosts[v.node] {
				minCosts[v.node] = cost
				heap.insert(Path{node: v.node, cost: cost})
			}
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i, cost := range minCosts {
		fmt.Fprintf(w, "%d %d\n", i, cost)
	}
	w.Flush()
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

// --- From ALDS1_9_C: Priority Queue

type Heap struct {
	size   int
	heap   []Path
	isHigh func(a, b Path) bool
}

func NewHeap(isHigh func(a, b Path) bool) Heap {
	heap := make([]Path, 1) // 先頭は不使用
	return Heap{size: 0, heap: heap, isHigh: isHigh}
}

func (h *Heap) insert(v Path) {
	h.size += 1
	if h.size > len(h.heap)-1 {
		h.heap = append(h.heap, v)
	} else {
		h.heap[h.size] = v
	}

	for i := h.size; i > 1; {
		parent := i / 2
		if h.isHigh(h.heap[parent], h.heap[i]) {
			break
		}
		h.heap[i], h.heap[parent] = h.heap[parent], h.heap[i]
		i = parent
	}
}

func (h *Heap) extractMax() Path {
	if h.size <= 0 {
		panic("cannot extract from empty heap")
	}

	max := h.heap[1]
	h.heap[1] = h.heap[h.size]
	h.size -= 1
	h.maxHeapify(1)

	return max
}

func (h *Heap) maxHeapify(idx int) {
	left := idx * 2
	right := left + 1
	largest := idx

	if left <= h.size {
		if h.isHigh(h.heap[left], h.heap[idx]) {
			largest = left
		}
		if right <= h.size && h.isHigh(h.heap[right], h.heap[largest]) {
			largest = right
		}
	}

	if largest != idx {
		h.heap[idx], h.heap[largest] = h.heap[largest], h.heap[idx]
		h.maxHeapify(largest)
	}
}

Python: import heapq

MAX = 10000
WHITE = 0
GRAY = 1
BLACK = 2
INF = float('inf')
color = [WHITE for _ in range(MAX)]
d = [INF for _ in range(MAX)]
adj = [None for _ in range(MAX)]
n = 0


def main():
    global n
    n = int(input())

    for _ in range(n):
        u, k, *n_s = map(int, input().split(' '))
        adj[u] = ([(n_s[2*j], n_s[2*j+1]) for j in range(k)])

    dijkstra(0)

    for i in range(n):
        print(f'{i} {d[i] if d[i] != INF else -1}')


def dijkstra(s):
    d[s] = 0

    pq = []

    heapq.heappush(pq, (0, s))

    while len(pq) > 0:
        f = heapq.heappop(pq)
        u = f[1]

        color[u] = BLACK
        if d[u] < f[0]:
            continue

        for j in range(len(adj[u])):
            v = adj[u][j][0]
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + adj[u][j][1]:
                d[v] = d[u] + adj[u][j][1]
                heapq.heappush(pq, (d[v], v))
                color[v] = GRAY


if __name__ == '__main__':
    main()

Python: import heapq

n = int(input())

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


def dijkstra(s):
    dist[s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[u[1]] < u[0]:
            continue

        for v in G[u[1]]:
            if check[v[0]] != 2:
                if dist[u[1]] + v[1] < dist[v[0]]:
                    dist[v[0]], check[v[0]] = dist[u[1]] + v[1], 1
                    heapq.heappush(pq, (dist[v[0]], v[0]))


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(data[1]):
            G[data[0]].append((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: #coding: utf-8

inf = 1000000000


def dijkstra(s):
    d = [inf for i in range(n)]
    color = ["white" for i in range(n)]
    p = [-1 for i in range(n)]
    d[s] = 0

    while True:
        mincost = inf
        for i in range(n):
            if color[i] != "black" and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == inf:
            break

        color[u] = "black"

        for v in range(n):
            if color[v] != "black" and mtrx[u][v] != False:
                if d[u] + mtrx[u][v] < d[v]:
                    d[v] = d[u] + mtrx[u][v]
                    p[v] = u
                    color[v] = "gray"
    return d

n = int(input())
mtrx = [[False for j in range(n)] for i in range(n)]
for i in range(n):
    data = list(map(int,input().split()))
    k = data[1]
    for num in range(k):
        mtrx[i][data[2+2*num]] = data[2+2*num+1]

d = dijkstra(0)

for i, num in enumerate(d):
    print(i,num)

Python: import queue

INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2

def dijkstra(n, adj):
    pq = queue.PriorityQueue()
    d = [INFTY] * n
    color = [WHITE] * n

    d[0] = 0
    pq.put((0, 0))
    color[0] == GRAY

    while not pq.empty():
        f = pq.get()
        u = f[1]
        color[u] = BLACK

        if d[u] < f[0]:
            continue

        for j in range(len(adj[u])):
            v = adj[u][j][0]
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + adj[u][j][1]:
                d[v] = d[u] + adj[u][j][1]
                pq.put((d[v], v))
                color[v] = GRAY

    for i in range(n):
        out = d[i]
        if out == INFTY:
            out = -1
        print('{0} {1}'.format(i, out))


n = int(input())
adj = [[] for i in range(n)]
for i in range(n):
    line = [int(v) for v in input().split()]
    u = line[0]
    k = line[1]
    for j in range(k):
        v = line[2*j + 2]
        c = line[2*j + 3]
        adj[u].append((v, c))

dijkstra(n, adj)

Python: import sys

def dijkstra(v_count: int, edges: list, start: int,
             *, adj_matrix: bool = False, unreachable=float("inf")) -> list:
    """ ダイクストラ法
    :param v_count: 頂点数
    :param edges: 辺のリスト(隣接リストor隣接行列)
    :param start: スタートする頂点
    :param adj_matrix: edgesに渡したリストが隣接行列ならTrue
    :param unreachable: 到達不能を表すコスト値
                        隣接行列の辺の有無の判定および返すリストの初期値に使用
    """
    from heapq import heappush, heappop

    vertices = [unreachable] * v_count
    vertices[start] = 0
    q, rem = [(0, start)], v_count - 1

    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1

        dests = (filter(lambda x: x[1] != unreachable, enumerate(edges[v]))
                 if adj_matrix else edges[v])

        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))

    return vertices

n = int(input())
inf = float("inf")
edges = [[inf]*n for _ in [0]*n]
for a in (tuple(map(int, l.split())) for l in sys.stdin):
    _from = a[0]
    for to, cost in zip(a[2::2], a[3::2]):
        edges[_from][to] = cost
vertices = dijkstra(n, edges, 0, adj_matrix=True)
for i, n in enumerate(vertices):
    print(i, n)