output_description: For each vertex, print its ID and the distance separated by a space character
  in a line respectively. Print in order of vertex IDs.
input_description: 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$).
attempt: import heapq
  
  
  class Edge:
      src = -1
      dest = -1
      cost = -1
  
  
  def Dijkstra(graph, s):
      INF = int(1e9)
      d = [INF] * len(graph)
      d[s] = 0
      used = [False] * len(graph)
      que = []
      heapq.heappush(que, (0, s))
      while len(que) != 0:
          val = heapq.heappop(que)
          v = val[1]
          if used[v]:
              continue
          used[v] = True
          for i in range(0, len(graph[v])):
              e = graph[v][i]
              if d[v] + e.cost < d[e.dest]:
                  d[e.dest] = d[v] + e.cost
                  heapq.heappush(que, (d[e.dest], e.dest))
      return d
  
  
  V = int(input())
  graph = [[] for i in range(0, V)]
  for i in range(0, V):
      vals = list(map(int, input().split(" ")))
      k = vals[1]
      for j in range(0, k):
          v = vals[2 + j * 2]
          c = vals[3 + j * 2]
          e = Edge()
          e.src = i
          e.dest = v
          e.cost = c
          graph[i].append(e)
  
  d = Dijkstra(graph, 0)
  for i in range(0, V):
      print(str(i) + " " + str(d[i]))
  
problem_description: 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$.
samples: [{"input": "5\n    0 3 2 3 3 1 1 2\n    1 2 0 2 3 4\n    2 3 0 3 3 1 4 1\n    3 4 2 1 0 1 1 4 4 3\n    4 2 2 1 3 3", "output": "0 0\n    1 2\n    2 2\n    3 1\n    4 3"}]