Go: package main

import (
	"fmt"
	"os"
	"bufio"
	"strings"
	"strconv"
)
var MAX = 1000000
type Vertex struct{
	Value int
	Routes map[int]int
	Done bool
}
func NewVertex(value int) *Vertex{
	routes := make(map[int]int)
	// for i, _ := range routes {
	// 	routes[i] = MAX
	// }
	return &Vertex{ value, routes, false }
}

func (v *Vertex) SetRoute(key, weight int) {
	v.Routes[key] = weight
}

type Path struct {
	Key int
	Weight int
}

var count = 0
func ShortestRoutes(list []*Vertex) []int {
	// create result table
	result  := make([]int, len(list))
	// fmt.Println(result)
	for i, _ := range result {
		result[i] = MAX
	}

	queue := make([]Path, 0)
	queue = append(queue, Path{0, 0})
	result[0] = 0

	for len(queue) != 0 {
		count++
		path := queue[0]
		queue = queue[1:]
		for key, weight := range list[path.Key].Routes {
			// fmt.Println(list[path.Key].Routes)
			// set to result
			// fmt.Printf("Path(%d, %d) ? result[%d] => %d, wieght: %d\n", path.Key, path.Weight, key, result[key], weight)
			if path.Weight + weight < result[key] {
				result[key] = path.Weight + weight 
				queue = append(queue, Path{key, result[key]})
			// } else if !list[key].Done {
			// 	queue = append(queue, Path{key, result[key]})
			}
		}
		list[path.Key].Done = true
	}
	return result
}
func main() {
	var n int
	fmt.Scanf("%d", &n)
	list := make([]*Vertex, n)
	scanner := bufio.NewScanner(os.Stdin)
	for i := 0; i < n; i++ {
		scanner.Scan()
		elements := strings.Split(scanner.Text(), " ")
		value, _ := strconv.Atoi(elements[0])
		list[i] = NewVertex(value)
		for j := 2; j < len(elements); j += 2 {
			key, _    := strconv.Atoi(elements[j])
			weight, _ := strconv.Atoi(elements[j + 1])
			list[i].SetRoute(key, weight)
		}
	}

	result := ShortestRoutes(list)
	for i := 0; i < len(result); i++ {
		fmt.Printf("%d %d\n", i, result[i]);
	}
	// fmt.Printf("count: %d\n", count)
}

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


def dijkstra(edges, start, *, adj_matrix=False, default_value=float('inf')):
    '''
    Returns best costs to each node from 'start' node in the given graph.
    (Single Source Shortest Path - SSSP)

    If edges is given as an adjacency list including costs and destination nodes on possible edges, adj_matrix should be False(default), and it is generally when this functions works much faster.

    Note that costs in edges should follow the rules below
    1. The cost from a node itself should be 0,
    2. If there is no edge between nodes, the cost between them should be default_value
    3. The costs can't be negative

    # sample input when given as adjacency list (adj_matrix=False)
    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0
             [(0, 2), (3, 3), (4, 6)],         # node 1
             [(0, 5), (3, 2), (5, 6)],         # node 2
             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3
             [(1, 6), (3, 2), (5, 4)],         # node 4
             [(2, 6), (4, 4)]]                 # node 5

    # sample input when given as adjacency matrix (adj_matrix=True)
    edges = [[0, 2, 5, 4, inf, inf],           # node 0
             [2, 0, inf, 3, 6, inf],           # node 1
             [5, inf, 0, 2, inf, 6],           # node 2
             [4, 3, 2, 0, 2, inf],             # node 3
             [inf, 6, inf, 2, 0, 4],           # node 4
             [inf, inf, 6, inf, 4, 0]]         # node 5
    '''

    n = len(edges)

    costs = [float('inf')] * n
    costs[start] = 0

    pq = [(0, start)]
    rem = n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) if adj_matrix else\
                    edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


def dijkstra_route(edges,
                   start,
                   goal,
                   *,
                   adj_matrix=False,
                   default_value=float('inf'),
                   verbose=False):
    '''
    Trys to find the best route to the 'goal' from the 'start'
    '''

    n = len(edges)

    costs = [float('inf')] * n
    costs[start] = 0
    pq = [(0, start)]
    rem = n - 1
    prevs = [-1 for _ in [None] * n]

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) if adj_matrix else\
                    edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))
                prevs[nxt_node] = tmp_node

    min_route = []
    prev = goal
    cnt = 0
    while prev != start:
        min_route.append(prev)
        prev = prevs[prev]

        cnt += 1
        if prev == -1 or cnt > n:
            raise NoRouteError(
                'There is no possible route in this graph \nedges: {} \nstart: {} \ngoal: {}'.
                format(edges, start, goal))

    else:
        min_route.append(prev)
    min_route = min_route[::-1]
    min_cost = costs[goal]

    if verbose:
        print('---route---')
        for node in min_route[:-1]:
            print('{} -> '.format(node), end='')
        else:
            print(min_route[-1])

        print('---distance---')
        print(min_cost)

    return costs, min_route


class NoRouteError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_C
    '''

    n = int(input())
    edges = [[] for i in range(n)]
    for i in range(n):
        i, k, *kedges = map(int, input().split())
        for edge in zip(kedges[::2], kedges[1::2]):
            edges[i].append(edge)

    costs = dijkstra(edges, 0)
    for i, cost in enumerate(costs):
        print(i, cost)

Python: import heapq

N = int(input())
A = [[]for i in range(N)]

for i in range(N):
    u, k, *nums = list(map(int,input().split()))
    for j in range(k):
        t = nums[j*2]
        c = nums[j*2+1]
        A[u].append([t, c])

memo = [1E18] * N
memo[0] = 0
qu = []
heapq.heappush(qu, (0,0))
while len(qu) != 0:
    atop = heapq.heappop(qu)
    for ne in A[atop[1]]:
        x = ne[0]
        next_cost = atop[0] + ne[1]
        if(memo[x] > next_cost):
            memo[x] = next_cost
            heapq.heappush(qu, (next_cost, x))
for i in range(N):
    print(i, memo[i])

Python: from heapq import heappush, heappop
INF = 10**10
a = int(input())
d = [[] for i in range(a)]
for i in range(a):
    tl = list(map(int,input().split()))
    ta , tb = tl[0],tl[1]
    t = 2
    for j in range(tb):
        tta,ttb = tl[t],tl[t+1]
        d[i].append((tta,ttb))
        t+=2

def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    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))
    for i in range(a):
        print(str(i)+" "+str(dist[i]))
dijkstra(a,d,0)

Python: from heapq import*
I=float("inf")
def m():
 n=int(input())
 A=[]
 for _ in[0]*n:
  e=list(map(int,input().split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[I]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()