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 sys
  
  readline = sys.stdin.readline
  write = sys.stdout.write
  
  N = int(readline())
  
  G = [None] * N
  W = 0
  for i in range(N):
      j, k, *V = map(int, readline().split())
      G[i] = [(v, c) for v, c in zip(V[::2], V[1::2])]
      if V:
          W = max(W, max(V[1::2]))
  
  
  def dial(N, G, W, s):
      B = [-1] * (N * W + 1)
      L = [-1] * (N * W + 1)
      (*prv,) = range(-1, N - 1)
      (*nxt,) = range(1, N + 1)
      nxt[-1] = -1
      prv[s + 1] = s - 1
      nxt[s - 1] = s + 1 if s < N - 1 else -1
      prv[s] = nxt[s] = -1
      B[0] = L[0] = s
      B[N * W] = +(s == 0)
      L[N * W] = N - 1 if s < N - 1 else N - 2
  
      dist = [N * W] * N
      dist[s] = 0
      for w in range(N * W):
          v = B[w]
          while v != -1:
              for x, c in G[v]:
                  e = w + c
                  if e < dist[x]:
                      d = dist[x]
                      dist[x] = e
  
                      p = prv[x]
                      n = nxt[x]
                      if p != -1:
                          nxt[p] = n
                      else:
                          B[d] = n
                      if n != -1:
                          prv[n] = p
                      else:
                          L[d] = p
  
                      l = L[e]
                      if l != -1:
                          nxt[l] = x
                      else:
                          B[e] = x
                      prv[x] = l
                      nxt[x] = -1
                      L[e] = x
              v = nxt[v]
      return dist
  
  
  dist = dial(N, G, W, 0)
  ans = []
  for i in range(N):
      ans.append("%d %d\n" % (i, dist[i]))
  sys.stdout.writelines(ans)
  
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"}]