Construction Project 2

문제

There are $NN$ stations in JOI Kingdom, numbered from $11$ to $NN$. There are $MM$ train lines in JOI Kingdom, numbered from $11$ to $MM$. The train line $ii$ (1 ≤ i ≤ M) connects station $A_{i}A\_i$ and station $B_{i}B\_i$ bi-directionally, and requires $C_{i}C\_i$ minutes for travel.

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

• You choose integers $uu$ and $vv$, which satisfy 1 &le; u < v &le; N. You construct a new train line, which connects station $uu$ and station $vv$ bi-directionally, and requires $LL$ minutes for travel. Note that you can choose $22$ integers such that there already be a train line connecting station $uu$ and station $vv$.

After you construct a new train line, the King of JOI Kingdom becomes happy if he can move from station $SS$ to station $TT$ within $KK$ 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}\backslash frac\{N(N-1)\}\{2\}$ ways when you choose $22$ integers $uu$ and $vv$, 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 $22$ integers that make the King happy.

입력

Read the following data from the standard input.

$NN$ $MM$

$SS$ $TT$ $LL$ $KK$

$A_{1}A\_1$ $B_{1}B\_1$ $C_{1}C\_1$

$A_{2}A\_2$ $B_{2}B\_2$ $C_{2}C\_2$

$\mathrm{⋮}\backslash vdots$

$A_{M}A\_M$ $B_{M}B\_M$ $C_{M}C\_M$

출력

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

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

4

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

3

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

0

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

16