Construction Project 2

Time limit2sMemory limit1024 MB

Summary

Count station pairs (u, v) where a new L-minute line between them lets the King reach T from S within K minutes.

Level: Medium6 of 10
Topics: Shortest path, Sorting, Binary search
Solved: No attempts yet

Problem

There are $N$ stations in JOI Kingdom, numbered from $1$ to $N$ . There are $M$ train lines in JOI Kingdom, numbered from $1$ to $M$ . Train line $i$ ( $1 \le i \le M$ ) connects station $A_i$ and station $B_i$ in both directions, and takes $C_i$ minutes to travel.

As a minister of JOI Kingdom, you decide to build a new train line as follows.

Choose integers $u$ and $v$ with $1 \le u < v \le N$ . Build a new train line that connects station $u$ and station $v$ in both directions, and takes $L$ minutes to travel. You may choose $u$ and $v$ even if a train line already connects them.

After the new line is built, the King becomes happy if he can move from station $S$ to station $T$ within $K$ minutes using the train lines. Transfer times and waiting times are not counted.

Count the pairs $(u, v)$ that make the King happy. There are $\frac{N(N-1)}{2}$ pairs in total.

Input

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

The second line contains $S$ , $T$ , $L$ , and $K$ .

Each of the next $M$ lines contains $A_i$ , $B_i$ , and $C_i$ .

Output

Print the number of pairs $(u, v)$ that make the King happy.

Constraints

$2 \le N \le 200\,000$
$1 \le M \le 200\,000$
$1 \le S < T \le N$
$1 \le L \le 10^9$
$1 \le K \le 10^{15}$
$1 \le A_i < B_i \le N$ ( $1 \le i \le M$ )
$(A_i, B_i) \ne (A_j, B_j)$ ( $1 \le i < j \le M$ )
$1 \le C_i \le 10^9$ ( $1 \le i \le M$ )
All given values are integers.

Examples4

Example 1

Input

Expected output

Example 2
Input
```
3 2
1 3 1 2
1 2 1
2 3 1
```
Expected output
```
3
```

Example 3

Input

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

Expected output

Example 4

Input

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

Expected output