建設事業 2

문제

JOI 国には $N$ 個の駅があり，$1$ から $N$ までの番号が付けられている．また，JOI 国には $M$ 本の鉄道路線があり，$1$ から $M$ までの番号が付けられている．鉄道路線 $i$ ($1 \le i \le M$) は駅 $A_i$ と駅 $B_i$ を双方向に結んでおり，その移動には $C_i$ 分を要する．

JOI 国の大臣であるあなたは，以下のように鉄道路線を新たに $1$ 本建設することにした．

• $1 \le u < v \le N$ を満たす整数 $u, v$ を選ぶ．駅 $u$ と駅 $v$ を双方向に結び，その移動に $L$ 分を要する鉄道路線を JOI 国に建設する．すでに駅 $u$ と駅 $v$ を双方向に結ぶ鉄道路線があってもよいことに注意せよ．

あなたが建設を行った後に，駅 $S$ から駅 $T$ までいくつかの鉄道路線を用いて $K$ 分以内に移動できるようになっている場合，国王は喜ぶ．なお，鉄道路線の乗り換え時間や待ち時間は考えないものとする．

建設する際の $2$ つの整数 $u, v$ の選び方は $\frac{N(N-1)}{2}$ 通りあるが，このうち国王が喜ぶような選び方が何通りあるかあなたは知りたい．

駅と鉄道路線，国王の要望の情報が与えられたとき，国王が喜ぶような $2$ つの整数の選び方が何通りあるかを求めるプログラムを作成せよ．

입력

入力は以下の形式で標準入力から与えられる．

N M
S T L K
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M

출력

標準出力に，国王が喜ぶような $2$ つの整数の選び方が何通りあるかを $1$ 行で出力せよ．

제한

• $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$)．
• 入力される値はすべて整数である．

서브태스크

1. ($8$ 点) $L = 1$，$K = 2$，$C_i = 1$ ($1 \le i \le M$)．
2. ($16$ 点) $N \le 50$，$M \le 50$．
3. ($29$ 点) $N \le 3\,000$，$M \le 3\,000$．
4. ($47$ 点) 追加の制約はない．

예제 입력 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

예제 출력 1

4

たとえば，あなたが $u = 3, v = 6$ と選んだとする．駅 $3$ と駅 $6$ を双方向に結び，その移動に $1$ 分を要する鉄道路線が JOI 国に建設される．

このとき，以下のようにして，駅 $6$ から駅 $7$ まで鉄道路線を用いて $2$ 分で移動できる．駅 $6$ から駅 $7$ まで $2$ 分以内に移動できるようになっているため，国王は喜ぶ．

1. 駅 $3$ と駅 $6$ を双方向に結ぶ路線を用いて，駅 $6$ から駅 $3$ に移動する．これには $1$ 分を要する．
2. 駅 $3$ と駅 $7$ を双方向に結ぶ路線を用いて，駅 $3$ から駅 $7$ に移動する．これには $1$ 分を要する．

国王が喜ぶような $2$ つの整数の選び方はこの場合を含めて $4$ 通りある．したがって，$4$ を出力する．

この入力例は小課題 $1, 2, 3, 4$ の制約を満たす．

예제 입력 2

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

예제 출력 2

3

あなたがどのように $2$ つの整数を選んでも，国王は喜ぶ．すなわち，国王が喜ぶような $2$ つの整数の選び方は $3$ 通りある．したがって，$3$ を出力する．

この入力例は小課題 $1, 2, 3, 4$ の制約を満たす．

예제 입력 3

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

예제 출력 3

0

あなたがどのように $2$ つの整数を選んでも，国王が喜ぶことはない．したがって，$0$ を出力する．

この入力例は小課題 $2, 3, 4$ の制約を満たす．

예제 입력 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

예제 출력 4

16

この入力例は小課題 $2, 3, 4$ の制約を満たす．