Background

Recently, "PlayerUnknown's Battlegrounds" has swept the globe, and Pipi and Maomao are also fascinated by this game. They often team up to play it.

In the game, Pipi and Maomao's favorite activity is blocking bridges, where a good opportunity can yield quite a few deliveries.

Of course, there are times when they cannot block the bridge, and Pipi and Maomao will choose to wait at other essential passageways.

Dr. K, being an elderly person with heart disease, naturally cannot play this game, but that doesn't stop him from conducting theoretical analyses of it. For instance, he is very interested in Pipi and Maomao's tactics recently.

Problem Description

The game map can be abstracted as a graph with $n$ nodes and $m$ undirected edges, with node numbers ranging from $1$ to $n$, and each edge having a positive integer length.

Assume that the big villain always starts from node $S$ and reaches node $T$ (where $S$ and $T$ are known), and only takes the shortest path. Pipi and Maomao will ambush the villain at nodes $A$ and $B$.

To ensure they can ambush the villain while also giving him a chance to escape, Pipi and Maomao stipulate that nodes $A$ and $B$ must satisfy:

• Among all possible paths of the villain, he must pass through either node $A$ or node $B$.
• Among all possible paths of the villain, there is no path that passes through both nodes $A$ and $B$.

Dr. K wants to know how many pairs of nodes $A$ and $B$ satisfy the above two conditions, considering that swapping the order of $A$ and $B$ counts as the same solution.

Input Format

The first line contains four integers $n, m, S, T (1 \le n \le 5 \times 10^{4}, 1 \le m \le 5 \times 10^{4}, 1 \le S, T \le n)$, as described in the problem.

The next $m$ lines each contain three integers $u, v, w (1 \le u, v \le n, 1 \le w \le 10^{9})$, indicating an edge of length $w$ connecting nodes $u$ and $v$.

Output Format

Output a single line containing the answer.

Sample Input and Output

Input Sample #1

7 7 1 7
1 2 2
2 4 2
4 6 2
6 7 2
1 3 2
3 5 4
5 7 2

Output Sample #1

6

Input Sample #2

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

Output Sample #2

3

Input Sample #3

6 7 1 4
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
1 6 2
6 4 2

Output Sample #3

5

Notes

Sample 1 Explanation

The valid pairs are $<2,3>, <2,4>, <4,3>, <4,5>, <6,3>, <6,5>$.

This problem is from the CodePlus 2017 November Contest, produced by the Student Algorithm and Competition Association of the Department of Computer Science and Technology, Tsinghua University.

Credit: Idea/Chen Yu, Problem Setting/Chen Yu, Problem Verification/Xing Jiankai

Git Repo: https://git.thusaac.org/publish/CodePlus201711

Thanks to Tencent for supporting this contest.

见题面 Input 部分

见题面 Output 部分