Problem:
Single Source Shortest Path II For a given weighted graph $G = (V, E)$, find the shortest path from a source to each vertex. For each vertex $u$, print the total weight of edges on the shortest path from vertex $0$ to $u$. Input In the first line, an integer $n$ denoting the number of vertices in $G$ is given. In the following $n$ lines, adjacency lists for each vertex $u$ are respectively given in the following format: $u$ $k$ $v_1$ $c_1$ $v_2$ $c_2$ ... $v_k$ $c_k$ Vertices in $G$ are named with IDs $0, 1, ..., n-1$. $u$ is ID of the target vertex and $k$ denotes its degree. $v_i (i = 1, 2, ... k)$ denote IDs of vertices adjacent to $u$ and $c_i$ denotes the weight of a directed edge connecting $u$ and $v_i$ (from $u$ to $v_i$). Output For each vertex, print its ID and the distance separated by a space character in a line respectively. Print in order of vertex IDs. Constraints  $1 \leq n \leq 10,000$  $0 \leq c_i \leq 100,000$  $|E| < 500,000$  All vertices are reachable from vertex $0$  Sample Input 1 5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3 Sample Output 1 0 0
1 2
2 2
3 1
4 3 Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
from heapq import heappop,heappush
INF = float("inf")
white = 0; gray = 1; black =2

def dijkstra(s):
    
    dist[s] = 0 
    heappush(PQ,(0,s))
    color[s] = gray

    while PQ:
        
        mincost,u = heappop(PQ)
        color[u] = black
        if dist[u] < mincost: continue 

        
        for v,cost in adj[u]:
            if color[v] == black: continue 
            if dist[v] > dist[u] + cost:
                dist[v] = dist[u] + cost
                heappush(PQ,(dist[v],v))
                color[v] = gray

if __name__ == "__main__":
    n = int(input())
    adj = [[] for _ in range(n)]
    for i in range(n):
        inp = [int(x) for x in input().split()]
        u = inp[0]
        for v,c in zip(inp[2::2],inp[3::2]): adj[u].append((v,c))
    color = [white]*n 
    dist = [INF]*n 
    PQ = []
    dijkstra(0)
    for i in range(n): print("{} {}".format(i,dist[i]))

Solution (Python):
import heapq

def Sigle_Source_Shortest_Path_2(adj_list, Cost, Color):

    Cost[0] = 0
    H = list()
    heapq.heappush(H, [0, 0])

    while len(H) != 0:
        _, u = heapq.heappop(H)
        Color[u] = "B"

        for i in range(len(adj_list[u])):

            c = adj_list[u][i][0]
            v = adj_list[u][i][1]
           
            if Color[v] != "B":
                if Cost[v] > Cost[u] + c:
                    Cost[v] = Cost[u] + c
                    Color[v] = "G"
                    heapq.heappush(H, [Cost[v], v])

def Main():
    N = int(input())
    adj_list = [list() for n in range(N)]
    Cost = [1000000 for n in range(N)]
    Color = ["W" for n in range(N)]

    for n in range(N):
        u, K, *p = map(int, input().split())

        if K > 0:
            for k in range(K):
                v, c = p[2*k], p[2*k + 1]
                adj_list[u].append([c, v])

    Sigle_Source_Shortest_Path_2(adj_list, Cost, Color)

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

Main()

Solution (Python):

from heapq import heappush, heappop

INF = 10**15
N = int(input())
W = [tuple(zip(*[map(int, input().split()[2:])]*2)) for _ in [0]*N]

H = []
checked = [False]*N
D = [INF]*N
D[0] = 0


heappush(H, (D[0], 0))

while H:
    d, v = heappop(H)
    checked[v] = True

    if D[v] < d:
        continue

    for u, w in W[v]:
        if not checked[u]:
            if D[v] + w < D[u]:
                D[u] = D[v] + w
                heappush(H, (D[u], u))


[print(i, d) for i, d in enumerate(D)]

Solution (Python):
import heapq

def main():

    INF = 1000000009
    n = int(input())
    e = [[] for _ in range(n)]
    for i in range(n):
        inf = list(map(int,input().split()))
        for j in range((inf[1])):
            e[inf[0]].append([inf[2+j*2],inf[2+j*2+1]])
    
    dp = [INF]*n
    dp[0] = 0
    pq = [[0,0]]
    heapq.heapify(pq)
    while pq:
        cost,v = heapq.heappop(pq)
        if dp[v]<cost:continue

        for i in range(len(e[v])):
            u = e[v][i][0]
            ncost = cost+e[v][i][1]
            if ncost < dp[u]:
                dp[u] = ncost
                heapq.heappush(pq,[ncost,u])
    for i in range(n):
        print(i,dp[i])


if __name__ == '__main__':
    main()

Solution (Python):
import queue

INFTY=1<<21


def dijkstra(n,EdgeMatrix,start):

    NodeList=queue.PriorityQueue() 
    Distance=[INFTY]*n 
    used=[False]*n 

    Distance[start]=0 
    used[start]=True 
    LastNode=start 
    count=1 

    while count<n:
        for i in range(len(EdgeMatrix[LastNode])):
            
            Edge=EdgeMatrix[LastNode][i]
            if used[Edge[0]]==False and Distance[Edge[0]]>Distance[LastNode]+Edge[1]:
                    Distance[Edge[0]]=Distance[LastNode]+Edge[1]
                    NodeList.put([Distance[Edge[0]],Edge[0]])

        
        while True:
            minNode=NodeList.get()
            if used[minNode[1]]==False:
                break

        LastNode=minNode[1] 
        used[minNode[1]]=True 
        count+=1 
    return Distance


n=int(input())


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


Distance=dijkstra(n,EdgeMatrix,0)

for node,distance in enumerate(Distance):
    print(node,distance)

Solution (Python):
import heapq


def dijkstra(n):
    inf=float("inf")
    color=["white" for _ in range(n)]
    D=[inf for _ in range(n)]
    P=[0 for _ in range(n)]
    M=[[] for _ in range(n)]

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

    D[0]=0
    P[0]=-1

    H=[(0,0)]
    heapq.heapify(H)

    while len(H)>=1:
        u=heapq.heappop(H)[1]
        if color[u]=="black":continue
        color[u]="black"

        V=[(i,j) for i,j in M[u] if color[i]!="black"]
        while len(V)!=0:
            for i,j in V:
                if D[u]+j<D[i]:
                    D[i]=D[u]+j
                    P[i]=u
                    color[i]="gray"
                    heapq.heappush(H,(D[i],i))
            break

    return D


for i,j in enumerate(dijkstra(int(input()))):
    print(i,j)

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop



BIG_NUM = 2000000000
HUGE_NUM = 9999999999999999
MOD = 1000000007
EPS = 0.000000001



class Edge:
    def __init__(self,arg_to,arg_cost):
        self.to = arg_to
        self.cost = arg_cost

class Info:
    def __init__(self,arg_node_id,arg_sum_cost):
        self.node_id = arg_node_id
        self.sum_cost = arg_sum_cost

    def __lt__(self,arg):
        return self.sum_cost < arg.sum_cost


V = int(input())
min_dist = [BIG_NUM]*V
G = [[] for i in range(V)]

for loop in range(V):
    node_id,tmp_num,*table = list(map(int,input().split()))
    for i in range(0,len(table),2):
        G[node_id].append(Edge(table[i],table[i+1]))


min_dist[0] = 0
Q = []

heappush(Q, Info(0,0))

while len(Q) > 0:
    info = heappop(Q)
    if info.sum_cost > min_dist[info.node_id]:
        continue
    for edge in G[info.node_id]:
        if min_dist[edge.to] > info.sum_cost+edge.cost:
            min_dist[edge.to] = info.sum_cost+edge.cost
            heappush(Q, Info(edge.to,min_dist[edge.to]))


for i in range(V):
    print("%d %d"%(i,min_dist[i]))

Solution (Python):
import heapq

class Pair:
    def __init__(self, num=None, wei=None):
        self.num = num
        self.wei = wei 
    def __str__(self):
        return str(self.num) + ' ' + str(self.wei)

def createAdjList():
    adjList = []
    for i in range(n):
        innerList = []
        u, k, *v = map(int, input().split())
        for j in range(0, k*2, 2):
            
            
            newPair = [v[j+1],v[j]]
            innerList.append(newPair)
        adjList.append(innerList)
    return adjList


def dijkstra():
    d[0] = 0
    pq = []
    pq.append([0,0])
    heapq.heapify(pq)

    while len(pq) > 0:
        
        uWei, uNum  = heapq.heappop(pq)

        status[uNum] = VISITED

        
        if d[uNum] < uWei:
            continue

        
        for v in adjList[uNum]:
            vNum = v[1]
            vWei = v[0]
            if status[vNum] != VISITED and d[uNum] + vWei < d[vNum]:
                d[vNum] = d[uNum] + vWei
                status[vNum] = VISITING
                heapq.heappush(pq, [d[vNum], vNum])

import sys


n = int(input())
NOT_VISITED = 0 
VISITING = 1 
VISITED = 2 
INFTY = 10**21

status = [NOT_VISITED] * n
d = [INFTY] * n
p = [-1] * n

adjList = createAdjList()
dijkstra()
for i in range(n):
    print(i, d[i])

Solution (Python):
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    import heapq
    from copy import deepcopy

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

    n = int(input())

    adj = [0]*n

    for _ in range(n):
        u, k, *vc = map(int, input().split())
        vc_tuple = [0]*k
        for i, (v, c) in enumerate(zip(vc[::2], vc[1::2])):
            
            vc_tuple[i] = (v, c)
        adj[u] = vc_tuple

    def dijkstra():
        d = [INFTY]*n
        color = [WHITE]*n

        d[0] = 0
        PQ = [(0, 0)]
        heapq.heapify(PQ) 
        color[0] = GRAY
        while PQ:  
            f = heapq.heappop(PQ)
            u = f[1]
            color[u] = BLACK

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

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

        for i in range(n):
            print(str(i) + ' ' + str(-1 if d[i] == INFTY else d[i]))

    dijkstra()

    """

    nodes = [[] for _ in range(n)]

    for _ in range(n):
        u, k, *vc = map(int, input().split())
        cv = [0]*k
        for i, (v, c) in enumerate(zip(vc[::2], vc[1::2])):
            cv[i] = (c, v)
        nodes[u] = cv

    d = [INFTY]*n
    d[0] = 0

    d_node = nodes[0]
    heapq.heapify(d_node)

    visited = [False]*n
    visited[0] = True

    while d_node:
        min_c, min_v = heapq.heappop(d_node)
        if visited[min_v]:
            continue
        visited[min_v] = True
        d[min_v] = min_c
        for c, v in nodes[min_v]:
            heapq.heappush(d_node, (min_c+c, v))

    for u, dist in enumerate(d):
        print(str(u) + ' ' + str(dist))
    """

Solution (Python):
import heapq

class ShortestPath:
    def __init__(self, V, E, start, INF = float('inf')):
        self.V = V
        self.E = E 
        self.dijkstra(start, INF)

    def dijkstra(self, start, INF):
        que = list()
        self.distance = [INF] * self.V
        self.prev = [-1] * self.V
        self.distance[start] = 0
        heapq.heappush(que, (0, start))

        while len(que) > 0:
            dist, fr = heapq.heappop(que)
            if self.distance[fr] < dist:
                continue
            for to, cost in self.E[fr]:
                if self.distance[fr] + cost < self.distance[to]:
                    self.distance[to] = self.distance[fr] + cost
                    heapq.heappush(que, (self.distance[to], to))
                    self.prev[to] = fr 


V = int(input())
edge = [[] for _ in range(V)]
for _ in range(V):
    u, _, *e = map(int, input().split())
    for t, d in zip(e[::2], e[1::2]):
        edge[u].append((t, d))

sp = ShortestPath(V, edge, 0)
for i, d in enumerate(sp.distance):
    print(i, d)

Solution (Python):
import sys
from heapq import *

MAX_INT= 10 ** 10

n = int(input())
adj_list = []

for _ in range(n):
  commands = sys.stdin.readline().split()
  lst = [ commands[i:i+2] for i in range(2, len(commands), 2)]
  adj_list.append(lst)

def dijkstra():
  
  visited = [False] * n
  dist_arr = [MAX_INT] * n
  pq = []
  prev = [None] * n

  
  pq = [(0, 0)]
  dist_arr[0] = 0

  while len(pq) > 0:
    dist, idx = heappop(pq)
    visited[idx] = True

    
    for edge in adj_list[idx]:
      cur_idx, cur_dist = [ int(e) for e in edge]
      if visited[cur_idx]: continue

      new_dist = dist + cur_dist

      if new_dist < dist_arr[cur_idx]:
        dist_arr[cur_idx] = new_dist
        heappush(pq, (dist_arr[cur_idx], cur_idx))

  return dist_arr

distArr = dijkstra()
for i in range(n):
  print(i, distArr[i])

Solution (Python):
import heapq
from collections import defaultdict

n = int(input())
graph = defaultdict(list)
for _ in range(n):
    u, k, *edges = map(int, input().split())
    for i in range(0, len(edges), 2):
        graph[u].append((edges[i], edges[i+1]))

q = [(0, 0)]
d = {}


while q:
    d_min, u = heapq.heappop(q)
    if u in d:
        continue
    d[u] = d_min
    for v, w in graph[u]:
        if v not in d:
            heapq.heappush(q, (d_min+w, v))

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

Solution (Python):
n = int(input())
INF = float("inf")
edges = [[] for _ in range(n)]
visited = [False]*n


d = [INF]*n
d[0] = 0

for _ in range(n):
    ls = list(map(int, input().split()))
    u = ls[0]
    degrees = ls[1]
    data = ls[2:]
  
    for i in range(degrees):
        v = data[i*2]
        cost = data[i*2+1]
        edges[u].append((v, cost))
        

















import heapq

heap = [(0, 0)]
d[0] = 0


while heap:
    du, u = heapq.heappop(heap)
    for v, cost in edges[u]:
        if du + cost < d[v]:
            d[v] = du +  cost
            
            heapq.heappush(heap, (d[v], v))

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

Solution (Python):
from heapq import heapify, heappush, heappop


n = int(input())

nodes = [[] * n for i in range(n)]
for _ in range(n):
    line = list(map(int, input().split()))
    u = line.pop(0)
    k = line.pop(0)
    for i in range(k):
        v = line.pop(0)
        c = line.pop(0)
        nodes[u].append((v, c))



inf = 100 * 100000 + 1

d = [inf] * n
V = set([i for i in range(n)]) 
S = set() 


start = 0
target = start
d[start] = 0

H = []



heappush(H, (start, d[start]))

while V != S:
    u, c = heappop(H)
    S.add(u)
    for v, c in nodes[u]:
        if d[u] + c < d[v]:
            d[v] = d[u] + c
            heappush(H, (v, d[v]))
    

for i in range(n):
    print(f"{i} {d[i]}")

Solution (Python):
from heapq import heappop, heappush

def dijkstra(s):
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return

INF = 10 ** 18
n = int(input())
cost = [[] for _ in range(n)]
used = [1] * n
dp = [INF] * n

for i in range(n):
    lst = list(map(int, input().split()))
    for j in range(lst[1]):
        v, c = lst[2 + (2 * j)], lst[3 + (2 * j)]
        cost[lst[0]].append([c, v])

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

Solution (Python):
from collections import deque

n = int(input())
g = []
d = [10**10] * n
d[0] = 0

for i in range(n):
    temp = list(map(int, input().split()))
    k = temp[1]
    temp = temp[2:]
    adj = []
    for j in range(k):
        v, c = temp[j*2], temp[j*2+1]
        adj.append([v, c])
    g.append(adj)




q = deque()

q.append((0, g[0]))
done = set()

while q:
    node = q.popleft()
    prev = node[0]
    adj = node[1]
    

    for next in adj:
        v = next[0]
        w = next[1]
        
        

        
        if d[prev] + w < d[v]:
            d[v] = d[prev] + w
            
            
            q.append((v, g[v]))
        if v not in done:
            done.add(v)
            q.append((v, g[v]))



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

Solution (Python):
import heapq


def dijkstra(adj_list, n):
    dist = [float("inf") for i in range(n)]
    visited = [False for _ in range(n)]
    parent = [-1 for _ in range(n)]
    start = 0
    dist[start] = 0
    dist_heap = []  
    heapq.heappush(dist_heap, (dist[start], start))

    while len(dist_heap) > 0:
        cost, start = heapq.heappop(dist_heap)  
        visited[start] = True
        if dist[start] < cost:  
            continue
        for end, weight in adj_list[start]:
            
            if not visited[end] and dist[start] + weight < dist[end]:
                dist[end] = dist[start] + weight
                parent[end] = start
                heapq.heappush(dist_heap, (dist[end], end))

    return parent, dist


def main():
    n = int(input())
    adj_list = []
    for _ in range(n):
        row = []
        line = input().split()
        dim = int(line[1])
        for i in range(dim):
            row.append((int(line[2 + i * 2]), int(line[2 + i * 2 + 1])))  
        adj_list.append(row)
    _, dist = dijkstra(adj_list, n)
    for i in range(n):
        print("{} {}".format(i, dist[i]))


if __name__ == "__main__":
    main()

Solution (Python):


import heapq

WHITE = 0
GRAY = 1
BLACK = 2

INF = 2000000000


def dijkstra():
    PQ = []
    heapq.heapify(PQ)
    color = [WHITE] * n
    d = [INF] * n
    
    d[0] = 0
    heapq.heappush(PQ, (0, 0))
    color[0] = GRAY
    
    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
    for i in range(n):
        print(i, d[i])


n = int(input())

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

dijkstra()

Solution (Python):
n = int(input())
adjacents = []
inf =  999999999999999
distances = [inf] * n
colors  = ["white"] * n
from heapq import heappush, heappop

for i in range(n):
  u, k, *a = map(int, input().split())
  adjacents.append([])
  for l in range(k):
    v = a[(l * 2)]
    c = a[(l * 2 + 1)]
    adjacents[u].append([v, c])

def dijkstra(u):
  distances[u] = 0
  queue = []
  heappush(queue, [0, u])

  while queue:
    w, u = heappop(queue)
    
    if distances[u] < w:
      continue
    
    colors[u] = "black"
    distances[u] = w

    for edge, weight in adjacents[u]:
      if colors[edge] != "black" and distances[edge] > weight + w:
        heappush(queue, [weight + w, edge])

dijkstra(0)

for index, edge in enumerate(distances):
  print(index, edge)

Solution (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()

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def dijkstra(n, start, nbl):
    """n: 頂点数, start: 始点, nbl: 隣接リスト"""
    import heapq
    WHITE = 1<<5
    GRAY = 1<<10
    BLACK = 1<<15
    INF = 1<<20
    color = [WHITE] * n
    distance = [INF] * n
    parent = [-1] * n
    q = []

    distance[start] = 0
    heapq.heappush(q, (0, start))
    while len(q) != 0:
        du, u = heapq.heappop(q)
        
        color[u] = BLACK
        if distance[u] < du:
            continue
        for next, cost in nbl[u]:
            if color[next] != BLACK and distance[u] + cost < distance[next]:
                distance[next] = distance[u] + cost
                color[next] = GRAY
                heapq.heappush(q, (distance[next], next))
    return distance


def main():
    n = int(input().strip())
    nb = [[] for _ in range(n)]
    for i in range(n):
        l = list(map(int, input().strip().split()))
        for j in range(l[1]):
            nb[i].append((l[2 + 2 * j], l[3 + 2 * j]))
    d = dijkstra(n, 0, nb)
    for i, v in enumerate(d):
        print(i, v)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N):
        u, k, *vc = (int(i) for i in input().split())
        for i in range(0, len(vc), 2):
            G[u].append((vc[i], vc[i+1]))
    d = [[(1 << 63)-1, i] for i in range(N)]
    from heapq import heapify, heappop, heappush

    def dijkstra(s):
        d[s][0] = 0
        que = [(d[s][0], s)]
        heapify(que)
        finished = set()
        while len(finished) < N:
            u = heappop(que)
            while u[1] in finished:
                u = heappop(que)
            if d[u[1]][0] < u[0]:
                print('yeah')
            for v, c in G[u[1]]:
                if v in finished:
                    continue
                if d[v][0] > u[0] + c:
                    d[v][0] = u[0] + c
                    heappush(que, (d[v][0], v))
            finished.add(u[1])
    dijkstra(0)
    for i, val in enumerate(d):
        print(i, val[0])


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush,heappop,heapify

n = int(input())
G = [[] for _ in range(n)]
info = []

for i in range(n):
    info =  list(map(int,(input().split())))[2:]
    for j in range(int((len(info))/2)):
        G[i].append((info[2*j],info[2*j+1]))

color = ["white" for _ in range(n)]
dist = [(1<<21) for _ in range(n)]
que = []

def dijkstra():
    dist[0] = 0
    que.append((0,0)) 
    while que:
        
        now = heappop(que)
        u = now[1]
        if dist[u] < now[0]:
            continue
        
        color[u] = "black"
        for j in range(len(G[u])):
            if dist[u] + G[u][j][1] < dist[G[u][j][0]]:
                heappush(que,(dist[u] + G[u][j][1],G[u][j][0]))
                dist[G[u][j][0]] = dist[u] + G[u][j][1]




dijkstra()

for i,dist in enumerate(dist):
    print(i,dist)

Solution (Python):

import sys
import heapq
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

n=int(input())
G=[[] for i in range(n)]
for _ in range(n):
    inp = list(map(int,input().split()))
    u,k=inp[:2]
    for i in range(k):
        G[u].append((inp[2+2*i],inp[3+2*i]))

def disktra(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v,c in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist

d=disktra(G,0)
for i in range(n):
    print(i,d[i])

Solution (Python):

import sys
import heapq

n = int(input())
G = [[] for _ in range(n)]
for i in range(n):
    u, k, *vc = list(map(int, sys.stdin.readline().strip().split()))
    for j in range(k):
        G[u].append([vc[j * 2], vc[j * 2 + 1]])

p = [] * n
c = ['white'] * n
d = [] * n
heapq.heappush(d, (0, 0))  

mindist = [float('inf')] * n
mindist[0] = 0

while d:
    now = heapq.heappop(d)[1]

    
    if c[now] == 'black':
        continue
    c[now] = 'black'

    for i in G[now]:
        if mindist[now] + i[1] < mindist[i[0]]:
            mindist[i[0]] = mindist[now] + i[1]
            heapq.heappush(d, [mindist[i[0]], i[0]])

for i in range(n):
    print('{} {}'.format(i, mindist[i]))

Solution (Python):
N = int(input())

E = [None] * N
for _ in range(N):
    u, k, *vs = map(int, input().split())
    E[u] = []
    for i in range(k):
        v, c = vs[i*2], vs[i*2+1]
        E[u].append((v, c))

import heapq

vis = [False] * N
inf = 1e9
d = [inf] * N
d[0] = 0
pq = [(0, 0)]
while pq:
    nv, ni = heapq.heappop(pq)
    if nv > d[ni]:
        continue
    d[ni] = nv
    vis[ni] = True
    for v, c in E[ni]:
        nc = d[ni] + c
        if not vis[v] and nc < d[v]:
            heapq.heappush(pq, (nc, v))

for v in range(N):
    print(v, d[v])

Solution (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)

Solution (Python):
from heapq import heappush, heappop

INF = 10000 * 100000

def dijkstra(s: int):
	d[s] = 0
	H = []
	for v in range(n):
		heappush(H, (d[v], v))
	while len(H) >= 1:
		_, u = heappop(H)
		color[u] = "BLACK"
		for v, c in M[u]:
			if color[v] != "BLACK" and d[u] + c < d[v]:
				d[v] = d[u] + c
				pi[v] = u
				color[v] = "GRAY"
				heappush(H, (d[v], v))

if __name__ == "__main__":
	n = int(input())
	G = []
	M = [[] for _ in range(n)]
	color = ["WHITE" for _ in range(n)]
	d = [INF for _ in range(n)]
	pi = [None for _ in range(n)]

	for _ in range(n):
		l = list(map(int, input().split()))
		u = l[0]
		k = l[1]
		for i in range(k):
			v = l[2 * (i + 1)]
			c = l[2 * (i + 1) + 1]
			M[u].append([v, c])
	dijkstra(0)
	for v in range(n):
		print(f"{v} {d[v]}")

Solution (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()

Solution (Python):
from heapq import heappush, heappop
from collections import deque

def main():
    V = int(input())
    q = []
    G = [deque() for i in range(V)]
    
    for i in range(V):
        tmp = list(map(int, input().split()))
        
        if tmp[0] == 0:
            for j in range(tmp[1]): heappush(q, (tmp[2+2*j:4+2*j][::-1]))
                
        else:
            for j in range(tmp[1]): G[tmp[0]].append(tmp[2+2*j:4+2*j])
            
    dist = [float('inf')] * V
    visited = [False] * V
    dist[0], visited[0] = 0, True
    
    while q:
        cost, v = heappop(q)
        
        if visited[v]: continue
    
        dist[v], visited[v] = cost, True
        for u, c in G[v]:
            if visited[u] or dist[u] < cost + c: continue
            heappush(q, [c+cost, u])
        
    for i in range(V): print(i, dist[i])
    
if __name__ == '__main__':
    main()

Solution (Python):
import heapq as hq

n=int(input())
da=[[] for i in range(n)]
for i in range(n):
    li=list(map(int,input().split()))
    for i in range(li[1]):
        da[li[0]].append([li[i*2+3],li[i*2+2]])
q=[]
ans=[-1 for i in range(n)]
ans[0]=0
for i in da[0]:
    hq.heappush(q,i)
while len(q)!=0:
    no=hq.heappop(q)
    if ans[no[1]] < 0:
        ans[no[1]]=no[0]
        for i in da[no[1]]:
            hq.heappush(q,[no[0]+i[0],i[1]])
for i in range(n):
    print("{} {}".format(i,ans[i]))

Solution (Python):
class RadixHeap:
    __slots__ = ["data", "last", "siz", "used"]

    
    def __init__(self, N, C):
        self.data = [[] for i in range(C.bit_length() + 1)]
        self.last = self.siz = 0
        self.used = [0]*N

    def push(self, x, key):
        
        self.siz += 1
        self.data[(x ^ self.last).bit_length()].append((x, key))

    def pop(self):
        data = self.data
        used = self.used
        
        if not data[0]:
            i = 1
            while not data[i]:
                i += 1
            d = data[i]
            new_last, new_key = min(d)
            used[new_key] = 1
            for val in d:
                x, key = val
                if used[key]:
                    self.siz -= 1
                    continue
                data[(x ^ new_last).bit_length()].append(val)
            self.last = new_last
            data[i] = []
        else:
            new_last, new_key = data[0].pop()
            used[new_key] = 1
            self.siz -= 1
        return new_last, new_key

    def __len__(self):
        return self.siz

import sys
readline = sys.stdin.readline
write = sys.stdout.write


N = int(readline())
G = [None] * N
for i in range(N):
    u, k, *V = map(int, readline().split())
    G[i] = [(v, c) for v, c in zip(V[::2], V[1::2])]

def dijkstra(N, G, s):
    que = RadixHeap(N, 10**9 + 1)

    dist = [10**18]*N
    dist[s] = 0
    que.push(0, s)
    while que:
        cost, v = que.pop()
        if dist[v] < cost:
            continue
        for w, c in G[v]:
            if cost + c < dist[w]:
                dist[w] = r = cost + c
                que.push(r, w)
    return dist
dist = dijkstra(N, G, 0)
write("\n".join("%d %d" % (i, d) for i, d in enumerate(dist)))
write("\n")

Solution (Python):
import heapq


def dijkstra(adj, s):
    INF = 200000
    n = len(adj)
    state, d, p = [False] * n, [INF] * n, [-1] * n
    d[s] = 0
    pq = [(d[s], s)]
    while pq:
        f, u = heapq.heappop(pq)
        state[u] = True
        if d[u] < f:
            continue
        for v, c in adj[u]:
            if state[v]:
                continue
            if d[u] + c < d[v]:
                d[v] = d[u] + c
                p[v] = u
                heapq.heappush(pq, (d[v], v))
    return d


def main():
    n = int(input())
    adj = [[] for _ in range(n)]
    for _ in range(n):
        u, _, *vc = map(int, input().split())
        for v, c in zip(vc[::2], vc[1::2]):
            adj[u].append((v, c))
    dist = dijkstra(adj, 0)
    for i, d in enumerate(dist):
        print(i, d)


if __name__ == '__main__':
    main()