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: from collections import defaultdict
  import heapq
  
  v_num = int(input())
  connect = defaultdict(list)
  
  for _ in range(v_num):
      que = [int(n) for n in input().split(" ")]
      connect[que[0]] = [
          [v, w] for v, w in zip(que[2 : len(que) : 2], que[3 : len(que) : 2])
      ]
      # weight_edge[que[0]] = {k:v for k, v in zip(que[2:len(que):2], que[3:len(que):2])}
  queue = []
  heapq.heapify(queue)
  heapq.heappush(queue, [0, 0])
  distance = [-1 for n in range(v_num)]
  went = 0
  visited = set()
  while went < v_num:
      q = heapq.heappop(queue)
      weight, here = q
      if here in visited:
          continue
      visited |= {here}
      went += 1
      distance[here] = weight
      for conn in connect[here]:
          if conn[0] not in visited:
              heapq.heappush(queue, [weight + conn[1], conn[0]])
  for i in range(v_num):
      print(i, distance[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"}]