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: from heapq import heapify, heappop, heappush
  
  N, M = map(int, input().split())
  S, T = map(int, input().split())
  Graph = [set() for i in range(N)]
  Edge = []
  mod = 10**9 + 7
  inf = float("inf")
  for i in range(N):
      Edge.append((i, i, 0))
  for i in range(M):
      a, b, c = map(int, input().split())
      Graph[a - 1].add((c, b - 1))
      Graph[b - 1].add((c, a - 1))
      Edge.append((a - 1, b - 1, c))
      Edge.append((b - 1, a - 1, c))
  
  
  def dijkstra(s, n, links):
      Visited = [False] * n
      Visited[s] = True
      cost = [inf] * n
      P = [0] * n
      P[s] = 1
      cost[s] = 0
      heap = [(0, s)]
      heapify(heap)
      while heap:
          hc, hp = heappop(heap)
          for c, p in links[hp]:
              if Visited[p]:
                  continue
              if c + hc < cost[p]:
                  cost[p] = c + hc
                  P[p] = P[hp]
                  heappush(heap, (cost[p], p))
              elif c + hc == cost[p]:
                  P[p] = (P[p] + P[hp]) % mod
              else:
                  Visited[p] = True
          Visited[hp] = True
      return cost, P
  
  
  cost_S, P_S = dijkstra(S - 1, N, Graph)
  cost_T, P_T = dijkstra(T - 1, N, Graph)
  D = cost_S[T - 1]
  List = []
  for a, b, c in Edge:
      if (
          cost_S[a] + c + cost_T[b] == D
          and cost_S[a] < D / 2
          and cost_T[b] < D / 2
          and c > 0
      ):
          List.append((P_S[a] * P_T[b]) % mod)
      if (
          cost_S[a] + c + cost_T[b] == D
          and cost_S[a] == D / 2
          and cost_T[b] == D / 2
          and c == 0
      ):
          List.append((P_S[a] * P_T[b]) % mod)
  Sum = 0
  for i in List:
      Sum = (Sum + i) % mod
  ans = 0
  for i, c in enumerate(List):
      ans = (ans + (Sum - List[i]) * List[i]) % mod
  print(ans)
  
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"}]