output_description: Print the answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      S T
      U_1 V_1 D_1
      U_2 V_2 D_2
      :
      U_M V_M D_M
attempt: def getLeftmostBit(n):
  
      m = 0
      while n > 1:
  
          n = n >> 1
          m += 1
  
      return m
  
  
  """ 
  /* Given the position of previous leftmost 
  set bit in n (or an upper bound on 
  leftmost position) returns the new 
  position of leftmost set bit in n */ 
  """
  
  
  def getNextLeftmostBit(n, m):
  
      temp = 1 << m
      while n < temp:
          temp = temp >> 1
          m -= 1
  
      return m
  
  
  # The main recursive function used by countSetBits()
  # def _countSetBits(n, m)
  
  
  # Returns count of set bits present in
  # all numbers from 1 to n
  def countSetBits(n):
  
      # Get the position of leftmost set
      # bit in n. This will be used as an
      # upper bound for next set bit function
      m = getLeftmostBit(n)
  
      # Use the position
      return _countSetBits(n, m)
  
  
  def _countSetBits(n, m):
  
      # Base Case: if n is 0, then set bit
      # count is 0
      if n == 0:
          return 0
  
      # /* get position of next leftmost set bit */
      m = getNextLeftmostBit(n, m)
  
      # If n is of the form 2^x-1, i.e., if n
      # is like 1, 3, 7, 15, 31, .. etc,
      # then we are done.
      # Since positions are considered starting
      # from 0, 1 is added to m
      if n == (1 << (m + 1)) - 1:
          return (m + 1) * (1 << m)
  
      # update n for next recursive call
      n = n - (1 << m)
      return (n + 1) + countSetBits(n) + m * (1 << (m - 1))
  
  
  # Driver code
  n = 17
  print("Total set bit count is", countSetBits(n))
  
problem_description: Statement
  
  We have a graph with N vertices and M edges, and there are two people on the
  graph: Takahashi and Aoki.
  
  The i-th edge connects Vertex U_i and Vertex V_i. The time it takes to
  traverse this edge is D_i minutes, regardless of direction and who traverses
  the edge (Takahashi or Aoki).
  
  Takahashi departs Vertex S and Aoki departs Vertex T at the same time.
  Takahashi travels to Vertex T and Aoki travels to Vertex S, both in the
  shortest time possible. Find the number of the pairs of ways for Takahashi and
  Aoki to choose their shortest paths such that they never meet (at a vertex or
  on an edge) during the travel, modulo 10^9 + 7.
samples: [{"input": "4 4\n    1 3\n    1 2 1\n    2 3 1\n    3 4 1\n    4 1 1", "output": "2\n    \n\nThere are two ways to choose shortest paths that satisfies the condition:\n\n  * Takahashi chooses the path 1 \\rightarrow 2 \\rightarrow 3, and Aoki chooses the path 3 \\rightarrow 4 \\rightarrow 1.\n  * Takahashi chooses the path 1 \\rightarrow 4 \\rightarrow 3, and Aoki chooses the path 3 \\rightarrow 2 \\rightarrow 1.\n\n* * *"}, {"input": "3 3\n    1 3\n    1 2 1\n    2 3 1\n    3 1 2", "output": "2\n    \n\n* * *"}, {"input": "3 3\n    1 3\n    1 2 1\n    2 3 1\n    3 1 2", "output": "2\n    \n\n* * *"}, {"input": "8 13\n    4 2\n    7 3 9\n    6 2 3\n    1 6 4\n    7 6 9\n    3 8 9\n    1 2 2\n    2 8 12\n    8 6 9\n    2 5 5\n    4 2 18\n    5 3 7\n    5 1 515371567\n    4 8 6", "output": "6"}]