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 heapq import heappop, heappush
  import sys
  
  
  class SSSP:
      """Given weighted graph, find Single Sorce Shortest Path from node 0.
  
      >>> st = SSSP([[(2, 3), (3, 1), (1, 2)], \
                     [(0, 2), (3, 4)], \
                     [(0, 3), (3, 1), (4, 1)], \
                     [(2, 1), (0, 1), (1, 4), (4, 3)], \
                     [(2, 1), (3, 3)]])
      >>> [st.weight(n) for n in range(5)]
      [0, 2, 2, 1, 3]
      """
  
      def __init__(self, graph):
          self.size = len(graph)
          self.tree = []
          self.weights = [0] * self.size
          self._search(graph)
  
      def weight(self, n):
          return self.weights[n]
  
      def _search(self, graph):
          h = []
          count = 1
          for i, w in graph[0]:
              heappush(h, (w, 0, i))
  
          while count < self.size:
              while len(h) > 0:
                  weight, src, dst = heappop(h)
                  if self.weights[dst] == 0 and dst > 0:
                      self.weights[dst] = weight
                      count += 1
                      self.tree.append((src, dst))
                      for i, w in graph[dst]:
                          if self.weights[i] == 0 and dst > 0:
                              heappush(h, (w + weight, dst, i))
                      break
  
  
  def run():
      n = int(input())
  
      nodes = [None] * n
      for line in sys.stdin:
          id_, deg, *edges = [int(i) for i in line.split()]
          nodes[id_] = []
          for _ in range(deg):
              tgt, wgt, *edges = edges
              nodes[id_].append((tgt, wgt))
  
      st = SSSP(nodes)
      for node in range(n):
          print("{} {}".format(node, st.weight(node)))
  
  
  if __name__ == "__main__":
      run()
  
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"}]