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


def dj(adjm, start):
    n = len(adjm)
    d = [float("inf")] * n
    d[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while(q):
        td, v = heapq.heappop(q)
        for k in adjm[v].keys():
            nd = td + adjm[v][k]
            if d[k] > nd:
                d[k] = nd
                heapq.heappush(q, (nd, k))
    return d


def main():
    n = int(input())
    
    adjm = [{} for _ in range(n)]
    for i in range(n):
        vdata = list(map(int, input().split()))
        for j in range(vdata[1]):
            v, c = vdata[j * 2 + 2], vdata[j * 2 + 3]
            adjm[i][v] = c
    ans = dj(adjm, 0)
    for i, d in enumerate(ans):
        print(i, d)


if __name__ == "__main__":
    main()

Solution (Python):

"""
Created on Sat Jul 14 19:11:44 2018

@author: maezawa
"""
infinity = 2*10**9

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

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

color = [0]*n
d = [infinity for _ in range(n)]
p = [0]*n
p[0] = -1
d[0] = 0

def dyk(s):
    cnt = 1
    cur = s
    candidates = set() 
    while True:
        for i, w in adj[cur]:
            if color[i] == 2:
                continue
            if d[i] > d[cur] + w:
                d[i] = d[cur] + w
                color[i] = 1
            candidates.add(i)
        min_d = infinity
        for j in candidates:
            if min_d > d[j]:
                min_node = j
                min_d = d[j]
        candidates.remove(min_node)
        p[min_node] = cur
        color[cur] = 2
        cur = min_node
        cnt += 1
        
        
        if cnt == n:
            break
    return

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

Solution (Python):

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 only include 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

    
    edges = [[0, 2, 5, 4, inf, inf],           
             [2, 0, inf, 3, 6, inf],           
             [5, inf, 0, 2, inf, 6],           
             [4, 3, 2, 0, 2, inf],             
             [inf, 6, inf, 2, 0, 4],           
             [inf, inf, 6, inf, 4, 0]]         

    
    edges = [[(1, 2), (2, 5), (3, 4)],         
             [(0, 2), (3, 3), (4, 6)],         
             [(0, 5), (3, 2), (5, 6)],         
             [(0, 4), (1, 3), (2, 2), (4, 2)], 
             [(1, 6), (3, 2), (5, 4)],         
             [(2, 6), (4, 4)]]                 
    '''

    n = len(edges)

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], 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)

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], 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_B
    '''

    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)

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

Solution (Python):
import sys

def dijkstra(v_count: int, edges: list, start: int,
             *, adj_matrix: bool = False, unreachable=float("inf")) -> list:
    """ ダイクストラ法
    :param v_count: 頂点数
    :param edges: 辺のリスト(隣接リストor隣接行列)
    :param start: スタートする頂点
    :param adj_matrix: edgesに渡したリストが隣接行列ならTrue
    :param unreachable: 到達不能を表すコスト値
                        隣接行列の辺の有無の判定および返すリストの初期値に使用
    """
    from heapq import heappush, heappop

    vertices = [unreachable] * v_count
    vertices[start] = 0
    q, rem = [(0, start)], v_count - 1

    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1

        dests = (filter(lambda x: x[1] != unreachable, enumerate(edges[v]))
                 if adj_matrix else edges[v])

        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))

    return vertices

n = int(input())
edges = [[] for _ in [0]*n]
for a in (tuple(map(int, l.split())) for l in sys.stdin):
    edges[a[0]] = tuple(zip(a[2::2], a[3::2]))
vertices = dijkstra(n, edges, 0)
for i, n in enumerate(vertices):
    print(i, n)

Solution (Python):
import sys

def dijkstra(v_count: int, edges: list, start: int,
             *, adj_matrix: bool = False, unreachable=float("inf")) -> list:
    """ ダイクストラ法
    :param v_count: 頂点数
    :param edges: 辺のリスト(隣接リストor隣接行列)
    :param start: スタートする頂点
    :param adj_matrix: edgesに渡したリストが隣接行列ならTrue
    :param unreachable: 到達不能を表すコスト値
                        隣接行列の辺の有無の判定および返すリストの初期値に使用
    """
    from heapq import heappush, heappop

    vertices = [unreachable] * v_count
    vertices[start] = 0
    q, rem = [(0, start)], v_count - 1

    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1

        dests = (filter(lambda x: x[1] != unreachable, enumerate(edges[v]))
                 if adj_matrix else edges[v])

        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))

    return vertices

n = int(input())
inf = float("inf")
edges = [[inf]*n for _ in [0]*n]
for a in (tuple(map(int, l.split())) for l in sys.stdin):
    _from = a[0]
    for to, cost in zip(a[2::2], a[3::2]):
        edges[_from][to] = cost
vertices = dijkstra(n, edges, 0, adj_matrix=True)
for i, n in enumerate(vertices):
    print(i, n)

Solution (Python):
from collections import deque
import sys
import heapq
n = int(input())
V = [[int(i) for i in input().split()] for _ in range(n)]
dis = [sys.maxsize for _ in range(n)]
dis[0] = 0
h = []
for i in range(n):
    heapq.heappush(h,(dis[i],i))
while(len(h)>0):
    node = heapq.heappop(h)
    tmp = node[1]
    for i in range(V[tmp][1]):
        ind = V[tmp][2*i+2]
        cos = V[tmp][2*i+3]
        if cos + dis[tmp] < dis[ind]:
            dis[ind] = cos + dis[tmp]
            heapq.heappush(h,(dis[ind],ind))
for i,j in enumerate(dis):
    print(i,j)

Solution (Python):
import sys
import heapq
n = int(input())
V = [[int(i) for i in input().split()] for _ in range(n)]
dis = [sys.maxsize for _ in range(n)]
dis[0] = 0
h = []
for i in range(n):
    heapq.heappush(h,(dis[i],i))
while(len(h)>0):
    node = heapq.heappop(h)
    tmp = node[1]
    for i in range(V[tmp][1]):
        ind = V[tmp][2*i+2]
        cos = V[tmp][2*i+3]
        if cos + dis[tmp] < dis[ind]:
            dis[ind] = cos + dis[tmp]
            heapq.heappush(h,(dis[ind],ind))
for i,j in enumerate(dis):
    print(i,j)

Solution (Python):


inf = 1000000000


def dijkstra(s):
    d = [inf for i in range(n)]
    color = ["white" 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 mtrx[u][v] != False:
                if d[u] + mtrx[u][v] < d[v]:
                    d[v] = d[u] + mtrx[u][v]
                    p[v] = u
                    color[v] = "gray"
    return d

n = int(input())
mtrx = [[False for j in range(n)] for i in range(n)]
for i in range(n):
    data = list(map(int,input().split()))
    k = data[1]
    for num in range(k):
        mtrx[i][data[2+2*num]] = data[2+2*num+1]

d = dijkstra(0)

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

Solution (Python):

n=int(input())
graph=[[0]*n for i in range(n)]



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


S=[0]*n

d=[999999]*n
d[0]=0

for loop in range(n):
    tmp_vertex=-1

    
    for j in range(n):
        if(S[j]==0):
            if(tmp_vertex!=-1):
                if(d[j] < d[tmp_vertex]):
                    tmp_vertex=j
            else:
                tmp_vertex=j
    
    
    S[tmp_vertex]=1

    
    for j in range(n):
        if(graph[tmp_vertex][j]!=0 and S[j]==0):
            d[j]=min([ d[j], d[tmp_vertex] + graph[tmp_vertex][j] ])

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

Solution (Python):


import sys
from heapq import heappush, heappop

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')


def dijkstra(N: int, nodes: list, src: int) -> list:
    
    
    res = [float('inf')] * N
    
    que = [(0, src)]
    res[src] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        for nxt, cost in nodes[cur]:
            
            if res[cur] + cost < res[nxt]:
                res[nxt] = res[cur] + cost
                
                heappush(que, (res[nxt], nxt))
    
    return res

N=INT()
nodes=[[] for i in range(N)]
for i in range(N):
    l=LIST()
    u=l[0]
    k=l[1]
    l=l[2:]
    for j in range(0, k*2, 2):
        nodes[u].append((l[j], l[j+1]))

ans=dijkstra(N, nodes, 0)
for i in range(N):
    print(i, ans[i])

Solution (Python):
from collections import namedtuple

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = 1e9


def bf(n, s, es):
    d = [inf for _ in range(n)]
    d[s] = 0
    while True:
        updated = False
        for e in es:
            if d[e.fr] != inf and d[e.fr] + e.cost < d[e.to]:
                updated = True
                d[e.to] = d[e.fr] + e.cost

        if not updated:
            break

    return d


n = int(input())

m = [[-1 for _ in range(n)] for _ in range(n)]
es = []
for i in range(n):
    fs = list(map(int, input().split()))
    ne = fs[1]
    for j in range(ne):
        v = fs[2+2*j]
        c = fs[2+2*j+1]
        m[i][v] = c
        es.append(Edge(i, v, c))


d = bf(n, 0, es)
for (i, di) in enumerate(d):
    print(i, di)

Solution (Python):
from collections import namedtuple

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = 1e9


def bellman_ford(n, start, edges):
    dists = [inf for _ in range(n)]
    dists[start] = 0
    while True:
        updated = False
        for e in edges:
            if dists[e.fr] != inf and dists[e.fr] + e.cost < dists[e.to]:
                updated = True
                dists[e.to] = dists[e.fr] + e.cost

        if not updated:
            break

    return dists


def dijkstra(n, costs):
    dists = [inf for _ in range(n)]
    dists[0] = 0
    determined = [False for _ in range(n)]

    while True:
        v, min_d = -1, inf
        for i in range(n):
            if determined[i]:
                continue
            if dists[i] < min_d:
                v, min_d = i, dists[i]

        if v == -1:
            break

        determined[v] = True

        for i in range(n):
            if determined[i] or costs[v][i] == -1:
                continue

            dists[i] = min(dists[i], dists[v] + costs[v][i])

    return dists


n = int(input())

m = [[-1 for _ in range(n)] for _ in range(n)]
es = []
for i in range(n):
    fs = list(map(int, input().split()))
    ne = fs[1]
    for j in range(ne):
        v = fs[2+2*j]
        c = fs[2+2*j+1]
        m[i][v] = c
        es.append(Edge(i, v, c))



d = dijkstra(n, m)
for (i, di) in enumerate(d):
    print(i, di)

Solution (Python):
from collections import namedtuple
import heapq

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = int(1e9)


def bellman_ford(n, start, edges):
    dists = [inf for _ in range(n)]
    dists[start] = 0
    while True:
        updated = False
        for e in edges:
            if dists[e.fr] != inf and dists[e.fr] + e.cost < dists[e.to]:
                updated = True
                dists[e.to] = dists[e.fr] + e.cost

        if not updated:
            break

    return dists


def dijkstra(n, costs):
    dists = [inf for _ in range(n)]
    dists[0] = 0

    queue = []
    for (i, d) in enumerate(dists):
        heapq.heappush(queue, (d, i))

    while len(queue) > 0:
        d, i = heapq.heappop(queue)
        if d > dists[i]:
            continue

        for v in range(n):
            if v == i or costs[i][v] == inf:
                continue

            if dists[i] + costs[i][v] < dists[v]:
                dists[v] = dists[i] + costs[i][v]
                heapq.heappush(queue, (dists[v], v))

    return dists


def warshall_floyd(n, costs):
    dists = [[costs[i][j] for j in range(n)] for i in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

    return dists


n = int(input())

m = [[inf if i != j else 0 for i in range(n)] for j in range(n)]
es = []
for i in range(n):
    fs = list(map(int, input().split()))
    ne = fs[1]
    for j in range(ne):
        v = fs[2+2*j]
        c = fs[2+2*j+1]
        m[i][v] = c
        es.append(Edge(i, v, c))




d = warshall_floyd(n, m)
for (i, di) in enumerate(d[0]):
    print(i, di)

Solution (Python):
n = int(input())
adjc_list = [[] for _ in range(n)]
INF = 99999999999999999999
V = [ele for ele in range(n)]
S = []
d = [INF] * n
p = [ele for ele in range(n)]

for i in range(n):
    tmp = [int(ele) for ele in input().split()]
    for j in range(1, tmp[1]*2, 2):
        v = tmp[j+1]
        w = tmp[j+2]
        adjc_list[i].append([w, v])
    adjc_list[i].sort()


def my_dijkstra_solver():
    root = 0  
    
    d = [INF] * n
    d[root] = 0
    VS = V

    
    while VS:
        
        u = VS[0]
        for i in VS:
            if d[i] < d[u]:
                u = i

        S.append(u)  

        
        VS.remove(u)
        for w, v in adjc_list[u]:
            if v in VS:
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    p[v] = u  

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


if __name__ == "__main__":
    my_dijkstra_solver()

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

Solution (Python):
INFTY = 100000000000000000000000000
n = int(raw_input())
graph = {}
for i in range(n):
    entry = map(int, raw_input().split(' '))
    u = entry[0]
    k = entry[1]
    graph[u] = {}
    for j in range(k):
        v = entry[2+j*2]
        c = entry[2+j*2+1]
        graph[u][v] = c

d = {}
visited = {}
for i in range(n):
    d[i] = INFTY
    visited[i] = False
s = 0
d[s] = 0
visited[s] = True

while True:
    for i in range(n):
        if not visited[i] and i in graph[s] and d[i] > d[s] + graph[s][i]:
            d[i] = d[s] + graph[s][i]
    mincost = INFTY
    minnode = -1
    for i in range(n):
        if not visited[i] and d[i] < mincost:
            mincost = d[i]
            minnode = i
    if mincost == INFTY: break
    visited[minnode] = True
    s = minnode


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

Solution (Python):

n = int(input())
inf = 100 * 100000

M = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
    L = list(map(int, input().split()))
    u = L[0]
    k = L[1]
    v = L[2::2]
    c = L[3::2]
    for j in range(k):
        M[u][v[j]] = c[j]

S = set()
V = set(range(n))
S.add(0)
d = [inf for i in range(n)]
d[0] = 0
count = 0
while len(V - S) != 0:
    T = V - S
    nd = [inf for i in range(n)]
    for s in S:
        for m, c in enumerate(M[s]):
            if d[s] + c < nd[m] and m in T:
                nd[m] = d[s] + c

    min_nd = min(nd)
    u = nd.index(min_nd)
    S.add(u)
    d[u] = min_nd


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

Solution (Python):

from heapq import heappop, heappush
n = int(input())
inf = 100 * 100000

M = [[] for i in range(n)]

for i in range(n):
    L = list(map(int, input().split()))
    u = L[0]
    k = L[1]
    v = L[2::2]
    c = L[3::2]
    for j in range(k):
        M[u].append((v[j], c[j]))
result = [0] * n
S = set()
V = set(range(n))
S.add(0)
d = []
for m in M[0]:
    heappush(d, (m[1], m[0]))
T = V - S

while len(T) != 0:
    c, v = heappop(d)
    while v in S:
        c, v = heappop(d)
    result[v] = c
    S.add(v)
    T.remove(v)
    for m in M[v]:
        if m[0] in T:
            heappush(d, (result[v] + m[1], m[0]))

for i, v in enumerate(result):
    print(i, v)

Solution (Python):


import sys

def parse():
  n = int(raw_input())
  A = []
  for line in sys.stdin:
    fields = line.split()
    u = int(fields.pop(0))
    k = int(fields.pop(0))
    edges = {}
    for i in range(k):
      edges[int(fields[2*i])] = int(fields[2*i + 1])
    A.append(edges)
  return A

def dijkstra(s, cost):
  V = len(cost)
  d    = [float("inf")] * V
  used = [False] * V
  d[s] = 0

  while True:
    v = -1
    for u in range(V):
      if not used[u] and (v == -1 or d[u] < d[v]):
        v = u
    if v == -1:
      break
    used[v] = True
    for u in range(V):
      if not u in cost[v]: continue
      d[u] = min(d[u], d[v] + cost[v][u])

  return d

if __name__ == "__main__":
  A = parse()
  d = dijkstra(0, A)
  for i in range(len(d)):
    print i, d[i]

Solution (Python):
n = input()

M = [[float("inf") for j in xrange(n)] for i in xrange(n)]
p = [-1 for i in xrange(n)]

for i in xrange(n):
    tmp = map(int, raw_input().split())
    for j in xrange(tmp[1]):
        M[i][tmp[(j + 1)*2]] = tmp[j*2 + 3]

def dijksrra(s):
    color = ["WHITE" for i in xrange(n)]
    d = [float("inf") for i in xrange(n)]

    d[s] = 0
    p[s] = -1

    while 1:
        mincost = float("inf")
        for i in xrange(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 xrange(n):
            if color[v] != "BLACK" and M[u][v] != float("inf"):
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[v] = "GRAY"

    for i in xrange(n):
        print "%d %d" % (i, d[i])


dijksrra(0)

Solution (Python):
n = input()

INFTY = 1000000
color = [0 for i in xrange(n)]
d = [INFTY for i in xrange(n)]
M = [[INFTY for i in xrange(n)] for i in xrange(n)]
p = [-1 for i in xrange(n)]

def SSSP1():
    d[0] = 0

    while True:
        cost = INFTY
        for i in xrange(n):
            if color[i] != 2 and d[i] < cost:
                cost = d[i]
                u = i
            
        if cost == INFTY:
            break
        color[u] = 2
    
        for v in xrange(n):
            if color[v] != 2 and M[u][v] != INFTY and d[u] + M[u][v] < d[v]:
                d[v] = d[u] + M[u][v]
                p[v] = u
                color[v] = 1
    
    for i in range(n):
        if d[i] != INFTY:
            print i, d[i]

for i in xrange(n):
    G = map(int, raw_input().split())
    for j in xrange(G[1]):
        M[G[0]][G[(j+1)*2]] = G[j*2+3]
SSSP1()

Solution (Python):
INFTY = 100000000
n = int( raw_input() )
graph = {}
for i in range(n):
  In = map( int , raw_input().split(' ') )
  u = In[0]
  k = In[1]
  graph[u] = {}
  for j in range(k):
    v = In[2+j*2]
    c = In[2+j*2+1]
    graph[u][v] = c
 
da = {}
visited = {}
for i in range(n):
  da[i] = INFTY
  visited[i] = False
s = 0
da[s] = 0
visited[s] = True
 
while True:
  for i in range(n):
    if not visited[i] and i in graph[s] and da[i] > da[s] + graph[s][i]:
      da[i] = da[s] + graph[s][i]
  cost = INFTY
  node = -1
  for i in range(n):
    if not visited[i] and da[i] < cost:
      cost = da[i]
      node = i
  if cost == INFTY: break
  visited[node] = True
  s = node
  
for i in range(n):
  print i,da[i]

Solution (Python):
INFTY = 100000000
n = int( raw_input() )
graph = {}
for i in range(n):
  In = map( int , raw_input().split(' ') )
  u = In[0]
  k = In[1]
  graph[u] = {}
  for j in range(k):
    v = In[2+j*2]
    c = In[2+j*2+1]
    graph[u][v] = c
 
da = {}
visited = {}
for i in range(n):
  da[i] = INFTY
  visited[i] = False
s = 0
da[s] = 0
visited[s] = True
 
while True:
  for i in range(n):
    if not visited[i] and i in graph[s] and da[i] > da[s] + graph[s][i]:
      da[i] = da[s] + graph[s][i]
  cost = INFTY
  node = -1
  for i in range(n):
    if not visited[i] and da[i] < cost:
      cost = da[i]
      node = i
  if cost == INFTY: 
    break
  visited[node] = True
  s = node
  
for i in range(n):
  print i,da[i]

Solution (Python):
n = int(raw_input())
a = [0 for i in xrange(n)]
adj = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
	a[i] = map(int,raw_input().split())
for i in xrange(n):
	for j in xrange(2, a[i][1]*2+1, 2):
		adj[a[i][0]][a[a[i][0]][j]] = a[a[i][0]][j+1]
MAX = 100000000
end = [1] * n
cost = [MAX] * n
cost[0] = 0
prev = [0] * n
start = 0
while 1:
	min = MAX
	next = -1
	end[start] = 0
	for i in xrange(n):
		if end[i]:
			if adj[start][i]:
				d = cost[start] + adj[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
	start = next
	if next < 0:
		break
for i in xrange(n):
	print i, cost[i]

Solution (Python):
n = int(input())
G = [[-1 for i in range(n)] for j in range(n)]
d = [999999 for i in range(n)]
  
for i in range(n):
    v = input().split()
    for j in range(int(v[1])):
        G[int(v[0])][int(v[2+2*j])] = int(v[3+2*j])

flag = [0] * n
tn = [0]
d[0] = 0
for k in range(n):
    for i in range(n):
        if i in tn:
            for j in range(n):
                if G[i][j] != -1:
                    if d[j] > d[i] + G[i][j]:
                        d[j] = d[i] + G[i][j]
                    if j not in tn:
                        tn.append(j)
  
for i in range(n):
    print(str(i) + " " + str(d[i]))

Solution (Python):
n = int(input())
G = [[-1 for i in range(n)] for j in range(n)]
d = [999999 for i in range(n)]
  
for i in range(n):
    v = input().split()
    for j in range(int(v[1])):
        G[int(v[0])][int(v[2+2*j])] = int(v[3+2*j])

flag = [0] * n
tn = [0]
d[0] = 0
for k in range(n):
    for i in range(n):
        if i in tn:
            for j in range(n):
                if G[i][j] != -1:
                    if d[j] > d[i] + G[i][j]:
                        d[j] = d[i] + G[i][j]
                    if j not in tn:
                        tn.append(j)
  
for i in range(n):
    print(str(i) + " " + str(d[i]))

Solution (Python):
from __future__ import division, print_function
from sys import stdin, maxint
 
 
def main():
    num = int(stdin.readline())
 
    y = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        y.append([(next(it), next(it)) for _ in xrange(next(it))])
 
    weight = [maxint] * num
    weight[0] = 0
    t = set(xrange(1, num))
    index = 0
 
    while t:
        for v, cost in y[index]:
            if v not in t:
                continue
            weight[v] = min(weight[v], cost + weight[index])
 
        index = min(t, key=lambda i: weight[i])
        t.remove(index)
 
    for i, d in enumerate(weight):
        print(i, d)
 
 
main()

Solution (Python):
def dijkstra(n):
    d = [None] * 100
    p = [None] * 100
    color = [None] * 100
    
    for i in xrange(n):
        d[i] = float('inf')
        p[i] = -1
        color[i] = 0
    
    d[0] = 0
    
    while(True):
        minv = float('inf')
        u = -1
        for i in xrange(n):
            if minv > d[i] and color[i] != 2:
                u = i
                minv = d[i]
        
        if u == -1:
            break
        
        color[u] = 2
        
        for v in xrange(n):
            if color[v] != 2 and data[u][v] != float('inf'):
                if d[v] > d[u] + data[u][v]:
                    d[v] = d[u] + data[u][v]
                    p[v] = u
                    color[v] = 1

    for i in xrange(n):
        if d[i] == float('inf'):
            print '%d %d' % (i, -1)
        else:
            print '%d %d' % (i, d[i])

n = input()
data = [None] * n
for i in xrange(n):
    data[i] = [float('inf')] * n
    line = map(int, raw_input().split())
    for j in xrange(1, line[1] + 1):
        v = line[2 * j]
        c = line[2 * j + 1]
        data[line[0]][v] = c
        
dijkstra(n)

Solution (Python):
n = input()
inf = 1000000000
M = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  str = map(int, raw_input().split())
  u = str[0]
  k = str[1]
  for j in range(k):
    v = str[2+2*j]
    c = str[3+2*j]
    M[u][v] = c
d = [inf for i in range(n)]
color = [0 for i in range(n)]
 
d[0] = 0
color[0] = 1
 
while 1:
  minv = inf
  u = -1
  for i in range(n):
    if minv>d[i] and color[i]!=2:
      u = i
      minv = d[i]
  if u == -1:
    break
  color[u] = 2
  for v in range(n):
    if color[v]!=2 and M[u][v]!=inf:
      if d[v]>d[u]+M[u][v]:
        d[v] = d[u] + M[u][v]
        color[v] = 1
for i in range(n):
  if d[i]==inf:
    print '%d -1' % i
  else:
    print '%d %d' % (i, d[i])

Solution (Python):
MAX = 100
INF = 1000000
WHITE = 0
GRAY = 1
BLACK = 2
n = int(raw_input())

M = [[INF for i in range(n)]for j in range(n)]
d = [INF for i in range(MAX)]
Color = [WHITE for i in range(MAX)]
for i in range(n):
    tmp = map(int,raw_input().split())
    u = tmp[0]
    k = tmp[1]
    for j in range(1, k + 1):
        v = tmp[j * 2]
        c = tmp[j * 2 + 1]
        M[u][v] = c


d[0] = 0
Color[0] = GRAY
    
while True:
    minv = INF
    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] != INF:
            if d[v] > d[u] + M[u][v]:
                d[v] = d[u] + M[u][v]
                Color[v] = GRAY
for i in range(n):
    print i,
    if d[i] == INF:
        print -1
    else:
        print d[i]

Solution (Python):
import heapq

n = int(input())
edges = [None] * n
for _ in range(n):
    l = list(map(int, input().split()))
    edges[l[0]] = set((c, j) for j, c in (l[i:i + 2] for i in range(2, l[1] * 2 + 2, 2)))

min_costs = [0] * n
visited = [False] * n
visited[0] = True
queue = list(edges[0])
heapq.heapify(queue)

while queue:
    total_cost, vertex = heapq.heappop(queue)
    if visited[vertex]:
        continue
    visited[vertex] = True
    min_costs[vertex] = total_cost
    for cost, vertex2 in edges[vertex]:
        if not visited[vertex2]:
            heapq.heappush(queue, (total_cost + cost, vertex2))

for r in enumerate(min_costs):
    print(*r)