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
  dic = {}
  nil = -1
  
  
  class Doubly:
      def __init__(self, key, l=nil, r=nil):
          self.l = l
          self.r = r
          self.key = key
  
      def Insert(self, key):
          obj = Doubly(key)
          obj.l = fake
          fakeR = fake.r
          fake.r = obj
          obj.r = fakeR
          fakeR.l = obj
          if key in dic.keys():
              dic[key].append(obj)
          else:
              dic[key] = [obj]
  
      def deleteFirst(self):
          fakeR = fake.r
          fake.r = fakeR.r
          fakeR.r.l = fake
          key = fakeR.key
          if dic != {}:
              dic[key].pop(0)
              if dic[key] == []:
                  del dic[key]
  
      def deleteLast(self):
          fakeL = fake.l
          fake.l = fakeL.l
          fakeL.l.r = fake
          key = fakeL.key
          if dic != {}:
              dic[key].pop(0)
              if dic[key] == []:
                  del dic[key]
  
      def Delete(self, target):
          if target in dic.keys():
              obj = dic[target].pop(0)
              objL = obj.l
              objR = obj.r
              objL.r = objR
              objR.l = objL
              if dic[target] == []:
                  del dic[target]
  
  
  n = int(input())
  
  fake = Doubly(nil)
  fake.l = fake
  fake.r = fake
  
  
  for i in range(n):
      data = list(input().split())
      order = data[0]
      if order == "insert":
          Doubly.Insert(Doubly, int(data[1]))
      elif order == "delete":
          Doubly.Delete(Doubly, int(data[1]))
      elif order == "deleteFirst":
          Doubly.deleteFirst(Doubly)
      else:
          Doubly.deleteLast(Doubly)
  
  obj = fake.r
  List = []
  while obj.key != -1:
      List.append(str(obj.key))
      obj = obj.r
  
  print(" ".join(List))
  
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"}]