問題文

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

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

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

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

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

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

制約

• 2 \leqq N \leqq 200\,000．
• 1 \leqq M \leqq 200\,000．
• 1 \leqq S < T \leqq N．
• 1 \leqq L \leqq 10^{9}．
• 1 \leqq K \leqq 10^{15}．
• 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M)．
• (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq M)．
• 1 \leqq C_i \leqq 10^9 (1 \leqq i \leqq M)．
• 入力される値はすべて整数である．

小課題

1. (8 点) L = 1，K = 2，C_i = 1 (1 \leqq i \leqq M)．
2. (16 点) N \leqq 50，M \leqq 50．
3. (29 点) N \leqq 3\,000，M \leqq 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 の制約を満たす．