Problem Description

Rabbit and Turtle decided to have a race on ARC Mountain.

ARC Mountain has $ N $ relay points, numbered from $ 1 $ to $ N $. There are also $ M $ paths connecting different pairs of relay points. No two paths connect the same pair of relay points. Each path has a defined length, and any two different relay points on ARC Mountain can be reached by traversing some paths.

In the race, one of the relay points is chosen as the destination $ A $, the starting point for Rabbit $ B $, and the starting point for Turtle $ C $. $ A, B, C $ must be different relay points. Once the race starts, Rabbit moves towards the destination at a speed of $ R $ meters per second, and Turtle moves at a speed of $ T $ meters per second.

Turtle wants to know how many combinations of $ A, B, C $ exist such that, by optimally moving, Turtle will always arrive at the destination after Rabbit, regardless of the path Rabbit takes.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ R $ $ T $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ : $ a_M $ $ b_M $ $ c_M $

• The first line contains the number of relay points $N\ (3\ ≦\ N\ ≦\ 2,500)$, the number of paths $M\ (2\ ≦\ M\ ≦\ 3,000)$, the speed of Rabbit $R\ (1\ ≦\ R\ ≦\ 200)$, and the speed of Turtle $T\ (1\ ≦\ T\ ≦\ 200)$, separated by spaces.
• The next $ M $ lines provide information about the paths. The $ i $-th line indicates that path $ i $ connects the two relay points $a_i, b_i\ (1\ ≦\ a_i\ ＜\ b_i\ ≦\ N)$ with a length of $c_i\ (1\ ≦\ c_i\ ≦\ 100)$ meters.

Output Format

Output the total number of combinations on one line. End the output with a newline.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #2

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

Sample Output #2

26

Notes/Hints

Sample Explanation 1

The following two cases are possible:
- If (destination, Rabbit's starting point, Turtle's starting point) is ($2,\ 4,\ 1$), Turtle arrives directly at the destination in $ 4 $ seconds. Meanwhile, Rabbit takes at least $ 4.5 $ seconds regardless of the path taken.
- If (destination, Rabbit's starting point, Turtle's starting point) is ($4,\ 3,\ 2$), Turtle arrives directly at the destination in $ 4 $ seconds. Meanwhile, Rabbit takes at least $ 4.5 $ seconds regardless of the path taken.
These are the two cases. Note that if (destination, Rabbit's starting point, Turtle's starting point) is ($1,\ 4,\ 3$), both Rabbit and Turtle need at least $ 3 $ seconds to reach the destination. If they move optimally, they arrive at the same time, so this does not satisfy the condition.

见题面 Input 部分

见题面 Output 部分