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: def E_dijkstra(V, AL, S):
      from heapq import heappush, heappop
  
      INF = float("inf")
      ans = [INF] * V
      ans[S] = 0
      used = [0] * V  # 0:未確定
      used[S] = 1
      que = []
      for i in range(V):
          heappush(que, (ans[i], i))
      while que:
          x, u = heappop(que)
          used[u] = 1
          for v, w in AL[u]:
              if not used[v] and ans[v] > x + w:
                  ans[v] = x + w
                  heappush(que, (ans[v], v))
      return ans
  
  
  # verified: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A
  # import sys
  # input = sys.stdin.readline
  # V,E,R=map(int,input().split())
  # AL=[[] for i in range(V)]
  # for _ in range(E):
  #     S,T,D=map(int,input().split())
  #     AL[S].append((T,D))
  # for ans in E_dijkstra(V,AL,R):
  #     print('INF' if ans==float('inf') else ans)
  
  import sys
  
  input = sys.stdin.readline
  
  N = int(input())
  AL = [[] for _ in range(N)]
  for _ in range(N):
      for i, x in enumerate(input().split()):
          x = int(x)
          if i == 0:
              j = x
          elif i == 1:
              pass
          else:
              if i % 2 == 0:
                  tmp = [x]
              else:
                  tmp.append(x)
                  AL[j].append(tmp)
  for ans in enumerate(E_dijkstra(N, AL, 0)):
      print(*ans)
  
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"}]