31624번 - Construction Project 2 서브태스크다국어

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$. The train line $i$ ($1 ≤ i ≤ M$) connects station $A_i$ and station $B_i$ bi-directionally, and requires $C_i$ minutes for travel.

You, a minister of JOI Kingdom, decided to construct a new train line as follows.

• You choose integers $u$ and $v$, which satisfy $1 ≤ u < v ≤ N$. You construct a new train line, which connects station $u$ and station $v$ bi-directionally, and requires $L$ minutes for travel. Note that you can choose $2$ integers such that there already be a train line connecting station $u$ and station $v$.

After you construct a new train line, the King of JOI Kingdom becomes happy if he can move from station $S$ to station $T$ within $K$ minutes by using some train lines. Note that transit times and waiting times for train lines are not considered.

There are $\frac{N(N-1)}{2}$ ways when you choose $2$ integers $u$ and $v$, and you want to know how many of these ways make the King happy.

Write a program which, given information of stations, the train lines, and the King’s request, calculates number of ways to choose $2$ integers that make the King happy.

Read the following data from the standard input.

$N$ $M$

$S$ $T$ $L$ $K$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_M$ $B_M$ $C_M$

Write one line to the standard output. The output should contain number of ways to choose $2$ integers that make the King happy.

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