Problem:
Single Source Shortest Path 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 100$  $0 \leq c_i \leq 100,000$  $|E| \leq 10,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):
import heapq


class Graph(object):

    class Node:
        def __init__(self, dist: int, number: int):
            self.dist = dist
            self.number = number

        def __lt__(self, other):
            return self.dist < other.dist \
                   or (self.dist == other.dist
                       and self.number < other.number)

        def __le__(self, other):
            return self.dist <= other.dist

        def __gt__(self, other):
            return other <= self

        def __ge__(self, other):
            return other < self

        def __str__(self):
            return "Node: (" + str(self.number) + ", " \
                   + str(self.dist) + ")"

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

        def __str__(self):
            return "Edge: (" + str(self.to) + ", " \
                   + str(self.cost) + ")"

    INF = 10e10

    def __init__(self, node_n: int, start: int):
        self.node_n = node_n
        self.start = start
        self.edges = [{} for _ in range(self.node_n)]
        self.dist = [self.INF for _ in range(self.node_n)]

    def set_edge(self, from_pos: int, to_pos: int, cost: int, reversible: bool) -> None:
        self.edges[from_pos][to_pos] = (self.Edge(to_pos, cost))
        if reversible:
            self.edges[to_pos][from_pos] = (self.Edge(from_pos, cost))

    def solve(self) -> list:
        raise NotImplementedError


class Dijkstra(Graph):
    hq = []
    prev: list

    def __init__(self, node_n: int, start: int):
        super(Dijkstra, self).__init__(node_n, start)
        self.dist[self.start] = 0
        self.prev = [None for _ in range(node_n)]

    def solve(self) -> list:
        heapq.heappush(self.hq, self.Node(0, self.start))

        while len(self.hq) != 0:
            node = heapq.heappop(self.hq)
            if node.dist > self.dist[node.number]:
                continue

            for edge in self.edges[node.number].values():
                alt = self.dist[node.number] + edge.cost
                if self.dist[edge.to] > alt:
                    self.dist[edge.to] = alt
                    self.prev[edge.to] = node.number
                    heapq.heappush(self.hq, self.Node(self.dist[edge.to], edge.to))

        return self.dist


if __name__ == '__main__':
    n = int(input())
    graph = Dijkstra(n, 0)

    for _ in range(n):
        buff = list(map(int, input().split()))
        u = buff[0]
        k = buff[1]
        for i in range(k):
            graph.set_edge(u,
                           buff[2 + i * 2],
                           buff[3 + i * 2],
                           False)
    dist = graph.solve()
    for i, d in enumerate(dist):
        print(i, d)

Solution (Python):
import sys
input = sys.stdin.readline



import heapq







def dijkstra(graph, start, n):
    INF = float('inf')
    memo = [INF] * n
    memo[start] = 0
    q = [(0, start)]

    while q:
        dist, ver = heapq.heappop(q)
        if memo[ver] < dist:
            continue
        for next_ver, next_dist in graph[ver]:
            if memo[next_ver] > dist + next_dist:
                memo[next_ver] = dist + next_dist
                heapq.heappush(q, (dist + next_dist, next_ver))

    return memo

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

memo = dijkstra(graph, 0, n)
for i, d in enumerate(memo):
    print(i, d)

Solution (Python):
import sys
import math

n = int(sys.stdin.readline())

Q = set()
out_edge = [set() for _ in range(n)]
weight = [[0] * n for _ in range(n)]

for _ in range(n):
    ll = list(map(int, sys.stdin.readline().split()))
    sn = ll[0]
    Q.add(sn)
    for j in range(ll[1]):
        en = ll[2+2*j]
        cn = ll[2+2*j+1]
        out_edge[sn].add(en)
        weight[sn][en] = cn

d = [0] + [math.inf for _ in range(n-1)]
prev = [None] * n

while len(Q)>0:
    minval = math.inf
    u = -1
    for q in Q:
        if minval > d[q]:
            minval = d[q]
            u = q
    if minval==math.inf:  break
    Q.remove(u)

    for v in out_edge[u]:
        if weight[u][v]>0:
            if d[v] > d[u] + weight[u][v]:
                d[v] = d[u] + weight[u][v]
                prev[v] = u

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

Solution (Python):
import sys
from collections import defaultdict


def main():
    n = int(input())
    lines = sys.stdin.readlines()
    vertex_weights = defaultdict(list)
    for i in range(n):
        u, k, *vtx_wght = map(int, lines[i].split())
        for v_i in range(k):
            vertex_weights[u].append((vtx_wght[2*v_i], vtx_wght[2*v_i+1]))

    dist_from_0 = {}
    vertices = [(0, 0)]
    while len(dist_from_0) != n:
        vertices.sort(key=lambda x: x[1], reverse=True)
        vtx, vtx_dist = vertices.pop()
        dist_from_0[vtx] = vtx_dist

        neighbor_vtx = vertex_weights[vtx]

        for n_vtx, n_dist in neighbor_vtx:
            if n_vtx not in dist_from_0.keys():
                vertices.append((n_vtx, vtx_dist + n_dist))

        [vertices.remove(x) for x in vertices[:] if x[0] in dist_from_0]


    answers = [None] * n
    sorted_dist = sorted(dist_from_0.items(), key=lambda x: x[0])
    for i in range(n):
        answers[i] = f"{sorted_dist[i][0]} {sorted_dist[i][1]}"
    [print(ans) for ans in answers]
    return


main()

Solution (Python):
from sys import stdin
from collections import deque

def read_graph(n):
    A = [ [-1]*(n+1) for _ in range(n+1) ]
    for _ in range(n):
        line = deque(stdin.readline().strip().split())
        u = line.popleft()
        line.popleft()
        for l, k in enumerate(line):
            if l % 2 == 0:
                v = k
            else:
                A[int(u)][int(v)] = int(k)
    return A

def dijkstra(n, A, s):
    color = [ 'WHITE' for i in range(n) ]
    d = [ float('inf') for i in range(n) ]
    d[s] = 0
    p = [-1] * n

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

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

        color[u] = 'BLACK'

        for v in range(n):
            if color[v] != 'BLACK' and A[u][v] != -1:
                if d[u] + A[u][v] < d[v]:
                    d[v] = d[u] + A[u][v]
                    p[v] = u
                    color[v] = 'GRAY'

    return d

n = int(input())
A = read_graph(n)
for i, k in enumerate(dijkstra(n, A, 0)):
    print(i, k)

Solution (Python):
from sys import maxsize

WHITE = 0
GRAY = 1
BLACK = 2


def read_adj():
    n = int(input())
    adj_list = [[] 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):
            adj_list[u].append((rest[i], rest[i + 1]))

    return n, adj_list


def shortest_path(n, adj_list):
    color = [WHITE] * n
    dist = [maxsize] * n

    dist[0] = 0
    color[0] = GRAY

    while True:
        minv = maxsize
        u = -1
        for i in range(n):
            if minv > dist[i] and color[i] != BLACK:
                u = i
                minv = dist[i]

        if u == -1:
            break
        color[u] = BLACK

        for v, c in adj_list[u]:
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                color[v] = GRAY
                
    return dist


def print_dist(dist):
    for u, d in enumerate(dist):
        print(u, d)


def main():
    n, adj_list = read_adj()
    dist = shortest_path(n, adj_list)
    print_dist(dist)


if __name__ == '__main__':
    main()

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 sys
def dijkstra(n, a):
	v = [False]*n
	v[0] = True
	w = [sys.maxsize] * n
	w[0] = 0
	while True:
		m = -1
		mini = sys.maxsize
		for i in range(n):
			for j in range(n):
				c = a[i][j]
				if v[i] and not v[j] and c != 0:
					w[j] = min(w[j], w[i]+c)
					if mini > w[j]:
						mini = w[j]
						m = j
		if m == -1: break
		v[m] = True
	
	for i in range(n):
		print(str(i) + ' ' + str(w[i]))

n = int(input())
a = [[0 for x in range(n)] for x in range(n)]
for i in range(n):
	t = list(map(int,input().split()))
	u = t[0]
	k = t[1]
	for j in range(k):
		v = t[(j*2)+2]
		c = t[(j*2)+3]
		a[u][v] = c
dijkstra(n, a)

Solution (Python):
import Queue

n = int(input())
alist = [[] for i in range(n)]

for i in range(n):
	arr = map(int,raw_input().split())
	v,k = arr[0],arr[1]
	for j in range(k):
		alist[v].append([arr[2+j*2+1],arr[2+j*2]])



dist = [float("inf") for i in range(n)]
dist[0] = 0

q = Queue.PriorityQueue()

q.put([dist[0],0])

while not q.empty():
	dist_u, u = q.get()

	if dist[u] < dist_u :
		continue

	for weight,v in alist[u]:
		alt = dist_u + weight
		if dist[v] > alt:
			dist[v] = alt
			q.put([alt,v])


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

Solution (Python):
INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2

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

    d[0] = 0
    color[0] == GRAY

    while True:
        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):
        out = d[i]
        if out == INFTY:
            out = -1
        print('{0} {1}'.format(i, out))


n = int(input())
m = [[INFTY] * n for i in range(n)]
for i in range(n):
    line = [int(v) for v in input().split()]
    u = line[0]
    k = line[1]
    for j in range(k):
        v = line[2*j + 2]
        c = line[2*j + 3]
        m[u][v] = c

dijkstra(n, m)

Solution (Python):
n=int(input())
d=[0]+[1e6]*n
c=[1]*n
M=[[-1]*n for _ in[0]*n]

for _ in[0]*n:
 data=list(map(int,input().split()))
 for i in range(data[1]):k=2*-~i;M[data[0]][data[k]]=data[k+1]

while 1:
 m,u=1e6,-1
 
 for i in range(n):
  if m>d[i]and c[i]:
      m,u=d[i],i
 if u<0:
     break
 c[u]=0
 
 for v in range(n):
  if c[v]and 1+M[u][v]and d[v]>d[u]+M[u][v]:
   d[v]=d[u]+M[u][v]
   
for i in range(n):
    print(i,d[i])

Solution (Python):
def dijkstra(s):
    color = ["white" for i in range(n)]

    d = [inf for i in range(n)]

    p = [-1 for i in range(n)]

    d[s] = 0

    while True:
        mincost = inf

        for i in range(n):
            if color[i] != "black" and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == inf:
            break

        color[u] = "black"

        for v in range(n):
            if color[v] != "black" and ci[u][v] != inf:
                if d[u] + ci[u][v] < d[v]:
                    d[v] = d[u] + ci[u][v]
                    p[v] = u
                    color[v] = "gray"
    return d


inf = 10 ** 9
n = int(input())
ci = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
    data = list(map(int, input().split()))
    u = data[0]
    k = data[1]

    for j in range(0, 2*k, 2):
        v, w = data[j+2], data[j+3]
        ci[u][v] = w

dList = dijkstra(0)

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

Solution (Python):
n = int(input())
a = []
for i in range(n):
    b = list(map(int, input().split()))
    c = [-1] * n
    for j in range(b[1]):
        c[b[2 + j * 2]] = b[3 + j * 2]
    a.append(c)

m = [float('inf')] * n
f = [0] * n
m[0] = 0
f[0] = 1
v = 0

for i in range(n-1) :
    for j in range(n) :
        if (a[v][j] + m[v] < m[j]) & (f[j] == 0) & (a[v][j] != -1):
            m[j] = a[v][j] + m[v]
    
    min = 2001
    minj = 0
    for j in range(n) :
        if (m[j] < min) & (f[j] == 0):
            min = m[j]
            minj = j
    
    v = minj
    f[minj] = 1

[print(i, m[i]) for i in range(n)]

Solution (Python):

import queue
nodelist={}
n=int(input())
dist={}
used={}
for i in range(n):
    line=list(map(int,input().split()))
    nodelist[line[0]]=[]
    dist[line[0]]=99999999
    used[line[0]]=False
    j=2
    while True:
        try:
            nodelist[line[0]].append((line[j],line[j+1]))
            j+=2
        except:
            break
q=queue.PriorityQueue()
dist[0]=0
for node in nodelist.keys():
    q.put((dist[node],node))

while not q.empty():
    node=q.get()
    if used[node[1]]:
        continue
    else:
        used[node[1]]=True
    for edge in nodelist[node[1]]:
        if dist[edge[0]]>dist[node[1]]+edge[1]:
            dist[edge[0]]=dist[node[1]]+edge[1]
            q.put((dist[edge[0]],edge[0]))

for d in dist.items():
    print(*d)

Solution (Python):

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)