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


if __name__ == '__main__':

    n = int(input())
    M = [[float("inf") for j in range(n)] for i in range(n)]

    for i in range(n):
        l = list(map(int, input().split(" ")))
        for k in range(l[1]):
            j = l[2 + 2 * k]
            c = l[2 + 2 * k + 1]
            M[i][j] = c

    d = [float("inf")] * n

    def dijkstra(s):
        color = [0] * n
        p = [None] * n
        d[s] = 0
        p[s] = -1

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

            if mincost == float("inf"):
                break

            color[u] = 2

            for v in range(n):
                if color[v] != 2:
                    if d[u] + M[u][v] < d[v]:
                        d[v] = d[u] + M[u][v]
                        p[v] = u
                        color[v] = 1

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

Python: import heapq


def dijkstra(g, source):
    n = len(g)
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (0, source))
    d = [float('inf') for _ in range(n)]
    d[source] = 0
    while len(q) > 0:
        cur = heapq.heappop(q)
        cur_pos = cur[1]
        for next in g[cur_pos]:
            next_pos = next[0]
            next_d = d[cur_pos] + next[1]
            if next_d < d[next_pos]:
                d[next_pos] = next_d
                heapq.heappush(q, (d[next_pos], next_pos))
    return d


def main():
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n):
        inp = list(map(int, input().split()))
        m = inp[0]
        k = inp[1]
        for i in range(k):
            g[m].append((inp[(i+1)*2], inp[(i+1)*2+1]))
    d = dijkstra(g, 0)
    for i in range(n):
        print(i, d[i])


if __name__ == '__main__':
    main()

Python: from heapq import heapify, heappush, heappop
INF = float("inf")
def MAIN():
    n = int(input())
    G = [[i, INF] for i in range(n)]
    G[0][1] = 0
    m = {}
    for _ in range(n):
        A = list(map(int, input().split()))
        m[A[0]] = {}
        for i in range(2, len(A), 2):
            m[A[0]][A[i]] = A[i + 1]
    dp = [(0, 0)]
    while dp:
        cost, u = heappop(dp)
        for v, c in m[u].items():
            if G[v][1] > G[u][1] + c:
                G[v][1] = G[u][1] + c
                heappush(dp, (G[v][1], v))
    print("\n".join(" ".join(map(str, a)) for a in G))
MAIN()

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
 
print(dijkstra())

Python: import sys
from collections import namedtuple
from heapq import heappop, heappush

Edge = namedtuple('Edage', 'to cost')
P = namedtuple('P', 'cost u')

N = int(input())

G = [[] for _ in range(N)]

for u in range(N):
  args = [int(x) for x in input().split()]
  #　不要な値を捨てる 
  args.pop(0)
  args.pop(0)

  while args:
    to = args.pop(0)
    cost = args.pop(0)
    G[u].append(Edge(to, cost))

costs = [sys.maxsize] * N
costs[0] = 0

q = [P(0, 0)]

while q:
  cost, u = heappop(q) 

  for v, c in G[u]:
    if costs[u] + c < costs[v]:
      costs[v] = costs[u] + c
      heappush(q, P(costs[v], v))

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

Python: import sys
from math import inf

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def SSSP(n, Adj):
    d = [inf] * n
    p = [-1] * n
    checked = [False] * n
    d[0] = 0
    checked[0] = True
    u = 0

    for i in range(n - 1):
        for v, cost in Adj[u]:
            if d[u] + cost < d[v]:
                p[v] = u
                d[v] = d[u] + cost

        min_n = 0
        min_w = inf
        for v in range(n):
            if not checked[v] and d[v] < min_w:
                min_n = v
                min_w = d[v]

        u = min_n
        checked[u] = True

    return d

def solve():
    n = int(input())
    Adj = [[] for i in range(n)]

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

    # debug(Adj, locals())

    d = SSSP(n, Adj)

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

if __name__ == '__main__':
    solve()

Python: # -*- coding: utf-8 -*-
from heapq import heappush, heappop

N = int(input())
INF = float("inf")
adj = []
for _ in range(N):
    inp = tuple(map(int, input().split()))
    adj.append(tuple(zip(inp[2::2], inp[3::2])))

checked = [False for _ in range(N)]
d = [float("inf") for _ in range(N)]
d[0] = 0

heap = [[0, 0]] # cost, vec

while heap:
    c, u = heappop(heap)
    if d[u] < c or checked[u]:
        continue
    for nu, nc in adj[u]:
        new_d = d[u] + nc
        if new_d < d[nu]:
            d[nu] = new_d
            heappush(heap, [d[nu], nu])
    checked[u] = True

for n in range(N):
    print("{} {}".format(n, d[n]))