Background

Recently, PlayerUnknown’s Battlegrounds (PUBG) has taken the world by storm. Pipi and Maomao have become obsessed with the game and often team up to play.

In the game, their favorite tactic is camping at bridges, where they can often secure lots of loot when the timing is right.

Of course, sometimes camping a bridge isn’t possible, so Pipi and Maomao will instead camp on other chokepoints.

Dr. K, being older and having a heart condition, naturally can’t play this game, but that doesn’t stop him from doing some theoretical analysis. Lately, he has been very interested in Pipi and Maomao’s tactics.

Problem 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