Description

The game map can be abstracted as an undirected graph with $n$ nodes and $m$ edges, numbered from $1$ to $n$. Each edge has a positive integer length.

Assume the “Da Mowang” will start from $S$ and reach $T$ (both $S$ and $T$ are known), and will only take shortest paths. Pipi and Maomao will ambush at points $A$ and $B$.

To ensure they can always ambush the Da Mowang while still leaving him a way out, $A$ and $B$ must satisfy:

• Among all possible shortest paths, the Da Mowang must pass through at least one of $A$ or $B$.
• Among all possible shortest paths, there does not exist a path that passes through both $A$ and $B$.

Dr. K wants to know how many pairs $(A, B)$ satisfy the two conditions above. Swapping $A$ and $B$ counts as the same plan.

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 above.

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

Output Format

Output a single line containing the answer.

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

6

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

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

5

Hint

Explanation for Sample 1:

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

From CodePlus November 2017, proudly presented by the Tsinghua University Student Association of Computer Science and Technology Algorithms and Programming Contest.

Credit: idea/Chen Yu, problem setting/Chen Yu, verification/Xing Jiankai.

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

Thanks to Tencent for supporting this contest.

Translated by ChatGPT 5