Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	g := makeGraph(n)
	for i := 0; i < n; i++ {
		u := getNextInt(scanner)
		k := getNextInt(scanner)
		for ii := 0; ii < k; ii++ {
			v := getNextInt(scanner)
			c := getNextInt(scanner)
			g[u][v] = c
		}
	}

	ans := make([]int, n)
	im := make(IntMap, 1)
	im.increment(0)
	for len(im) < n {
		min := 1 << 30
		x := -1
		for u := range im {
			for v := 0; v < n; v++ {
				if im.get(v) != 0 {
					continue
				}
				if min > ans[u]+g[u][v] {
					min = ans[u] + g[u][v]
					x = v
				}
			}
		}
		im.increment(x)
		ans[x] = min
	}

	for i := 0; i < n; i++ {
		fmt.Fprintln(writer, fmt.Sprintf("%d %d", i, ans[i]))
	}
	writer.Flush()
}

func makeGraph(n int) [][]int {
	g := make([][]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for ii := 0; ii < n; ii++ {
			g[i][ii] = 1 << 30
		}
	}

	return g
}

// IntMap ...
type IntMap map[int]int

func (m IntMap) get(key int) int {
	if _, ok := m[key]; ok {
		return m[key]
	}
	return 0
}
func (m IntMap) increment(key int) {
	if _, ok := m[key]; ok == false {
		m[key] = 0
	}
	m[key]++
}

Python: n = int(input())
adjc_list = [[] for _ in range(n)]
INF = 99999999999999999999
V = [ele for ele in range(n)]
S = []
d = [INF] * n
p = [ele for ele in range(n)]

for i in range(n):
    tmp = [int(ele) for ele in input().split()]
    for j in range(1, tmp[1]*2, 2):
        v = tmp[j+1]
        w = tmp[j+2]
        adjc_list[i].append([w, v])
    adjc_list[i].sort()


def my_dijkstra_solver():
    root = 0  # given
    # 1. 初期化
    d = [INF] * n
    d[root] = 0
    VS = V

    # 2. 以下の処理を、S = Vになるまで繰り返す
    while VS:
        # 2.1. V-S の中から、 d[u] が最小である頂点 u を選択する。
        u = VS[0]
        for i in VS:
            if d[i] < d[u]:
                u = i

        S.append(u)  # 2.2. u を S に追加する.
        # 2.3. u に隣接し, かつ V-S に属するすべての頂点 v に対する以下の値を更新する
        VS.remove(u)
        for w, v in adjc_list[u]:
            if v in VS:
                if d[v] > d[u] + w:
                    d[v] = d[u] + w
                    p[v] = u  # 親をどこかで使うのはわかるが一旦忘れよう

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


if __name__ == "__main__":
    my_dijkstra_solver()

Python: from heapq import heappop, heappush
from collections import defaultdict


class Dijkstra:
    """Graph input:
    {
    node:{node:cost,node:cost...},
    node:{node:cost,node:cost...},
    ...
    }
    """

    def __init__(self, graph: dict, N: int):
        self.graph = graph
        self.costs = [float("inf")] * N

    def calculate(self, start):
        queue = list()

        # step1: push the start point into the priority queue
        self.costs[start] = 0
        heappush(queue, (0, start))  # (cost,node)

        while queue:
            # step2: get the minimum cost node from unfixed node and fix the cost
            cost_from_start, min_node = heappop(queue)

            # step3: update the direct connected nodes
            for link, cost in self.graph[min_node].items():
                if cost_from_start + cost < self.costs[link]:
                    self.costs[link] = cost_from_start + cost
                    heappush(queue, (self.costs[link], link))

        return self.costs


n = int(input())
graph = defaultdict(dict)

for _ in range(n):
    data = [int(i) for i in input().split()]
    u = data[0]
    count = data[1]
    for j in range(1, count + 1):
        v = data[2 * j]
        w = data[2 * j + 1]
        graph[u][v] = w

dijkstra = Dijkstra(graph, n)
costs = dijkstra.calculate(0)

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

Python: INF = 1.0e+6
WHITE = 0
BLACK = 1

def dijkstras(M):
    n = len(M)
    d = [INF] * n
    color = [WHITE] * n

    d[0] = 0

    while True:
        minv = INF
        u = -1
        for i in range(n):
            if d[i] < minv and color[i] != BLACK:
                u = i
                minv = d[i]

        if u == -1:
            break

        color[u] = BLACK

        for v in range(n):
            if color[v] != BLACK and M[u][v] != INF:
                if d[v] > d[u] + M[u][v]:
                    d[v] = d[u] + M[u][v]

    for i in range(n):
        print("{} {}".format(i, -1 if d[i] == INF else d[i]))


if __name__ == "__main__":
    n = int(input())
    M = [[INF] * n for i in range(n)]

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

    dijkstras(M)

Python: from heapq import heappush, heappop
import math
def dijkstra(N, G, s):
    dist = [math.inf] * N
    que = [(0,s)]
    dist[s] = 0
    ans = [[] for i in range(N)]
    while que:
        c,v = heappop(que)
        if dist[v] < c:
            
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que,(dist[t],t))
    return dist
n = int(input())

g = [[]for i in range(n)]
for i in range(n):
    nums=list(map(int,input().split()))
    node=nums[0]
    for j in range(nums[1]):
        t=nums[j*2+2]
        c=nums[j*2+3]
        g[node].append([t,c])
   
ans = dijkstra(n,g,0)
for i in range(n):
    print(f'{i} {ans[i]}')

Python: INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2
 
n = int(input())
M = [list(map(int, input().split())) for i in range(n)]
 
d = [INFTY for i in range(n)]
color = [INFTY for i in range(n)]
 
for i in range(n):
    u = int(input())
    k = int(input())
    for j in range(k):
        v = int(input())
        c = int(input())
        M[u][v] = c
        
def dijkstra():
    global M, d, p, color
    d[0] = 0
    color[0] = GRAY
    while(1):
        minv = INFTY
        u = -1
        for i in range(n):
            if (minv > d[i] and color[i] != BLACK):
                u = i
                minv = d[i]
        if (u == -1):
            break
        color[u] = BLACK
        for v in range(n):
            if (color[v] != BLACK and M[u][v] != INFTY):
                if (d[v] > d[u] + M[u][v]):
                    d[v] = d[u] + M[u][v]
                    color[v] = GRAY
    for i in range(n):
        print(str(i) + " " + str(d[i]))
print(dijkstra())

Python: # Graph II - Single Source Shortest Path I
def dijkstra(length, adj_m):
    INFTY = float('inf')
    d = [INFTY for _ in range(length)]
    d[0] = 0
    Q = [i for i in range(length)]
    while Q:
        idx = INFTY
        minv = INFTY
        for q in Q:
            if d[q] < minv:
                idx, minv = q, d[q]
        u = Q.pop(Q.index(idx))
        for i, v in enumerate(adj_m[u]):
            if not v == -1:
                if d[i] > d[u] + v:
                    d[i] = d[u] + v
    return d

n = int(input())
adj_m = [[-1 for _ in range(n)] for _ in range(n)]
for _ in range(n):
    ss = list(map(int, input().split()))
    u, k = ss[0], ss[1]
    for i in range(k):
        vi,ci = ss[2*i+2], ss[2*i+3]
        adj_m[u][vi] = ci
d = dijkstra(n, adj_m)
for i,v in enumerate(d): print(i,v)