AT_joi2024ho_b 建設事業 2 (Construction Project 2)

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 $ つの整数の選び方が何通りあるかを求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ 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 $

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

### 小課題 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 $ 点) 追加の制約はない． --- ### Sample Explanation 1 たとえば，あなたが $ 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 $ の制約を満たす． --- ### Sample Explanation 2 あなたがどのように $ 2 $ つの整数を選んでも，国王は喜ぶ．すなわち，国王が喜ぶような $ 2 $ つの整数の選び方は $ 3 $ 通りある．したがって， $ 3 $ を出力する． この入力例は小課題 $ 1,2,3,4 $ の制約を満たす． --- ### Sample Explanation 3 あなたがどのように $ 2 $ つの整数を選んでも，国王が喜ぶことはない．したがって， $ 0 $ を出力する． この入力例は小課題 $ 2,3,4 $ の制約を満たす． --- ### Sample Explanation 4 この入力例は小課題 $ 2,3,4 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．