Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

//make priority queue
type Item struct {
	id       int
	priority int // this state is priority and distans from start
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// we want the ascending-priority-queue.
// So we use less than here.
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = j
	pq[j].index = i
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 //for safety
	*pq = old[0 : n-1]
	return item
}

func (pq *PriorityQueue) update(dist int, id int) {
	for _, i := range *pq {
		if i.id == id {
			if i.priority > dist {
				i.priority = dist
			}
		}
	}
}

// the main code
func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	return n
}

func dikstra(dist [][]int, n int) []int {
	// preparate priority queue
	inf := 1 << 30
	pq := make(PriorityQueue, n)
	shortests := make([]int, n)
	for i := 0; i < n; i++ {
		pq[i] = &Item{
			id:       i,
			priority: inf,
			index:    i,
		}

		shortests[i] = inf
	}
	pq[0].priority = 0
	shortests[0] = 0

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		shortests[item.id] = item.priority
		for id, d := range dist[item.id] {
			if d != -1 {
				pq.update(item.priority+d, id)
			}
		}
		heap.Init(&pq)
	}
	return shortests
}

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

	// init
	n := nextInt(sc)
	dist := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, n)
		for j := 0; j < n; j++ {
			dist[i][j] = -1
		}
	}

	// std Input
	for i := 0; i < n; i++ {
		u := nextInt(sc)
		k := nextInt(sc)
		for j := 0; j < k; j++ {
			v, c := nextInt(sc), nextInt(sc)
			dist[u][v] = c
		}
	}

	shortests := dikstra(dist, n)
	for i, d := range shortests {
		fmt.Printf("%d %d\n", i, d)
	}
}

Python: import io, sys, itertools
f = sys.stdin
 
 
def take2(iterable):
    i = iter(iterable)
    while True:
        yield next(i), next(i)
 
 
n = int(f.readline())
adj =[[(v, c) for v, c in take2(map(int, f.readline().split()[2:]))] for _ in range(n)]
d = [100000 * 100 + 1] * n
 
d[0] = 0
def search(parent, children):
    global d
    for v, c in children:
        if d[v] > d[parent] + c:
            d[v] = d[parent] + c
            search(v, adj[v])
     
search(0, adj[0])
     
for i in range(n):
    print(i, d[i])

Python: from sys import maxsize
from heapq import heappop, heappush


class Node:
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self):
        self.adjs = []
        self.color = Node.WHITE
        self.dist = maxsize

    def __lt__(self, other):
        return self.dist < other.dist

    def __repr__(self):
        return "Node({},{},{})".format(self.adjs, self.color, self.dist)


def read_adj():
    n = int(input())
    nodes = [Node() for _ in range(n)]

    for i in range(n):
        u, _, *rest = [int(x) for x in input().split()]
        for i in range(0, len(rest) - 1, 2):
            nodes[u].adjs.append((rest[i], rest[i+1]))

    return nodes


def shortest_path(nodes):
    h = []

    nodes[0].dist = 0
    nodes[0].color = Node.GRAY
    heappush(h, (0, 0))

    while len(h) > 0:
        min_node, min_dist = heappop(h)
        if nodes[min_node].dist < min_dist:
            continue

        nodes[min_node].color = Node.BLACK

        for adj, c in nodes[min_node].adjs:
            if nodes[min_node].color == Node.BLACK:
                continue
            if nodes[min_node].dist + c < nodes[adj].dist:
                nodes[adj].dist = nodes[min_node].dist + c
                nodes[adj].color = Node.GRAY
                heappush(h, (adj, nodes[adj].dist))


def print_dist(nodes):
    for u, n in enumerate(nodes):
        print(u, n.dist)


def main():
    nodes = read_adj()
    shortest_path(nodes)
    print_dist(nodes)


if __name__ == '__main__':
    main()

Python: import heapq as hq

def relax(u, v, w):
    if D[u] + w < D[v]:
        D[v] = D[u] + w
        P[v] = u
        hq.heappush(H, (D[v], v))

INF = float('inf')
N = int(input())
D = [INF for i in range(N)]
P = [None for i in range(N)]
D[0] = 0

G = [{} for i in range(N)]
for i in range(N):
    x = list(map(int, input().split()))
    g = x[2:]
    for j, n in enumerate(g):
        if j % 2 == 0:
            G[i][n] = g[j + 1]

H = [(0, 0)]

while 0 < len(H):
    d_u, u = hq.heappop(H)
    for v, w in G[u].items():
        relax(u, v, w)

for i, d in enumerate(D):
    print('{0} {1}'.format(i, d))

Python: from sys import stdin
import heapq
INF = 1<<21
n = int(stdin.readline())
adj = [[]] * n
for u in range(0, n):
    U = list(map(int, stdin.readline().split()))
    adj[u] = zip(U[2::2], U[3::2])
def dijkstra():
    d = [0] + [INF] * (n - 1)
    hq = [(0, 0)]
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in adj[u]:
            alt = d[u] + c
            if d[v] > alt:
                d[v] = alt
                heapq.heappush(hq, (alt, v))
    for i, c in enumerate(d):
        print(i, c)
dijkstra()

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[0]*n))
m()

Python: import heapq
import sys

input = sys.stdin.readline
INF = 100100100

class Info:
    def __init__(self, argNodeId, argSumCost):
        self.nodeId = argNodeId
        self.sumCost = argSumCost
    def __lt__(self, arg):
        return self.sumCost < arg.sumCost


class Edge:
    def __init__(self, argTo, argCost):
        self.to = argTo
        self.cost = argCost


def main():
    n = int(input())
    minDist = [INF] * n
    graph = [[] for _ in range(n)]
    for _ in range (n):
        u, k, *cv = map(int, input().split())
        for i in range(k):
            graph[u].append(Edge(cv[2 * i], cv[2*i + 1]))
    minDist[0] = 0
    Q = []
    heapq.heappush(Q, Info(0, 0))
    while len(Q) > 0:
        u = heapq.heappop(Q)
        if u.sumCost > minDist[u.nodeId]:
            continue
        for edge in graph[u.nodeId]:
            if minDist[edge.to] > u.sumCost + edge.cost:
                minDist[edge.to] = u.sumCost + edge.cost
                heapq.heappush(Q, Info(edge.to, minDist[edge.to]))
    for i in range(n):
        print('{} {}'.format(i, minDist[i]))


if __name__ == '__main__': main()

Python: from heapq import*
I=float("inf")
def m():
 n=int(input())
 A=[[]]*n
 for _ in range(n):
  e=list(map(int,input().split()))
  A[e[0]]=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))
 for i in range(n):print(i,d[i])
m()