Problem Description

In the country of JOI, there are $N$ train stations numbered from $1$ to $N$. Additionally, there are $M$ bidirectional railway lines numbered from $1$ to $M$. The railway line $i\ (1 \leq i \leq M)$ connects train station $A_{i}$ and train station $B_{i}$, and it takes $C_i$ minutes to travel from one station to the other.

As the minister of JOI, you decide to build a new railway line in the following manner:

Choose two integers $u, v\ (1 \leq u < v \leq N)$, and construct a bidirectional railway line between train station $u$ and train station $v$, which takes $L$ minutes to travel from one station to the other. Note that even if there is already a railway line connecting train station $u$ and train station $v$, you can still construct this new line.

If, after constructing this railway line, it is possible to travel from train station $S$ to train station $T$ in no more than $K$ minutes, the king will be pleased. We do not consider transfer times and waiting times.

Given the information about the train stations, railway lines, and the king's requirements, write a program to determine how many ways of choosing integers $u$ and $v$ will make the king happy.

Input Format

The first line contains two integers $N$ and $M$.

The second line contains four integers $S, T, L, K$.

The next $M$ lines each contain three integers $A_i, B_i, C_i$, representing the $i$-th bidirectional railway line.

Output Format

Output a single integer, representing the number of ways to choose integers $u$ and $v$ that will make the king happy.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

3 2
1 3 1 2
1 2 1
2 3 1

Sample Output #2

3

Sample Input #3

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

Sample Output #3

0

Sample Input #4

18 21
4 8 678730772 3000000062
5 13 805281073
8 17 80983648
3 8 996533440
10 16 514277428
2 5 57914340
6 11 966149890
8 12 532734310
2 9 188599710
2 3 966306014
12 16 656457780
16 18 662633078
1 15 698078877
2 8 665665772
2 6 652261981
14 15 712798281
7 13 571169114
13 14 860543313
6 7 454251187
9 14 293590683
6 14 959532841
3 11 591245645

Sample Output #4

16

Notes/Hints

For all input data, the following conditions are satisfied:

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq S < T \leq N$
• $1 \leq L \leq 10^9$
• $1 \leq K \leq 10^{15}$
• $1 \leq A_{i} < B_{i} \leq N\ (1 \leq i \leq M)$
• $(A_{i}, B_{i}) \neq (A_{j}, B_{j})\ (1 \leq i < j \leq M)$
• $1 \leq C_{i} \leq 10^9\ (1 \leq i \leq M)$

The detailed subtask additional restrictions and scores are as follows:

见题面 Input 部分

见题面 Output 部分