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: # -*- coding: utf-8 -*-
  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
  
      # sample input when given as adjacency matrix (adj_matrix=True)
      edges = [[0, 2, 5, 4, inf, inf],           # node 0
               [2, 0, inf, 3, 6, inf],           # node 1
               [5, inf, 0, 2, inf, 6],           # node 2
               [4, 3, 2, 0, 2, inf],             # node 3
               [inf, 6, inf, 2, 0, 4],           # node 4
               [inf, inf, 6, inf, 4, 0]]         # node 5
  
      # sample input when given not as adjacency matrix (adj_matrix=False)
      edges = [[(1, 2), (2, 5), (3, 4)],         # node 0
               [(0, 2), (3, 3), (4, 6)],         # node 1
               [(0, 5), (3, 2), (5, 6)],         # node 2
               [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3
               [(1, 6), (3, 2), (5, 4)],         # node 4
               [(2, 6), (4, 4)]]                 # node 5
      """
  
      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)
  
problem_description: 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$.
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"}]