Ambush on the Devil

You are given an undirected weighted graph with n vertices and m edges. The vertices are numbered from 1 to n, and each edge has a positive integer length. In the game story, the devil always travels from vertex \(S\) to vertex \(T\) along a shortest path (note that there may be multiple different shortest paths). Two heroes plan to ambush the devil. They will hide at vertices \(A\) and \(B\) respectively. To ensure that they catch the devil while still leaving him one escape route, they agree that the pair \(\{A, B\}\) must satisfy the following conditions:

• Every shortest \(S\)-\(T\) path contains at least one of \(A\) or \(B\) (i.e. the set \(\{A, B\}\) is a hitting set for the set of all shortest paths).
• No shortest \(S\)-\(T\) path contains both \(A\) and \(B\). (That is, on every shortest path, exactly one of \(A\) and \(B\) appears.)

Your task is to count the number of unordered pairs \(\{A, B\}\) that satisfy the above conditions.

Notes:

• A vertex \(v\) lies on some shortest \(S\)-\(T\) path if and only if \(d_S(v) + d_T(v) = d_S(T)\), where \(d_S(v)\) is the shortest distance from \(S\) to \(v\) and \(d_T(v)\) is the shortest distance from \(v\) to \(T\).
• If we denote by \(dp[v]\) the number of shortest paths from \(S\) to \(v\), and by \(dp_{rev}[v]\) the number of shortest paths from \(v\) to \(T\), then the total number of shortest paths from \(S\) to \(T\) is \(dp[T]\). A necessary condition for a candidate pair \(A, B\) is that
  
  \(dp[A] \times dp_{rev}[A] + dp[B] \times dp_{rev}[B] = dp[T]\).
  
  Moreover, if there is any shortest path that contains both \(A\) and \(B\), then the pair is invalid.

It is recommended to first run Dijkstra’s algorithm from both \(S\) and \(T\) (on the reversed graph) to compute \(d_S(\cdot)\) and \(d_T(\cdot)\). Then, consider the directed acyclic graph (DAG) defined by all edges \((u,v)\) satisfying \(d_S(u) + w(u,v) = d_S(v)\) with \(u,v\) on some shortest path (i.e. \(d_S(u) + d_T(u) = d_S(T)\) and similarly for \(v\)). Use dynamic programming on this DAG to compute \(dp\) and \(dp_{rev}\). Finally, you can test every unordered pair \(\{A, B\}\) of vertices that lie on some shortest \(S\)-\(T\) path to see if they meet the two conditions.

inputFormat

The first line contains four integers \(n\), \(m\), \(S\) and \(T\) (\(1 \leq S, T \leq n\)).

Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\) representing an undirected edge connecting vertices \(u\) and \(v\) with weight \(w\) (\(1 \leq w \leq 10^9\)).

outputFormat

Output a single integer representing the number of unordered pairs \(\{A, B\}\) that satisfy the ambush conditions.

sample

4 4 1 4
1 2 1
2 4 1
1 3 1
3 4 1

1