(duongmoi.*)

Có \(n\) ga xe lửa ở vương quốc LHP, các ga được đánh số thứ tự từ \(1\) đến \(n\). Có \(m\) con đường xe lửa hai chiều trong vương quốc được đánh số thứ tự từ 1 đến \(m\). Con đường thứ \(i\ (1 \leq i \leq m)\) nối ga \(a_{i}\) và \(b_{i}\) với thời gian \(c_{i}\) phút di chuyển.

An là kiến trúc sư trưởng của vương quốc quyết định xây dựng thêm một con đường sắt hai chiều như sau:

+ Chọn hai ga \(u\) và \(v\) thỏa mãn \(1 \leq u < v \leq n.\) Xây dựng mới một con đường nối hai ga này với thời gian di chuyển qua nó là \(l\) phút. Lưu ý, An vẫn có thể chọn xây dựng con đường mới nối hai ga \(u,\ v\) ngay cả khi giữa hai ga này đã có con đường xe lửa.

Sau khi An xây dựng xong con đường xe lửa mới, vua của vương quốc LHP thấy hạnh phúc nếu ông ấy có thể di chuyển từ ga \(s\) đến ga \(t\) với thời gian không quá \(k\) phút bằng cách đi qua các con đường xe lửa đã cho. Chú ý, thời gian chuyển và đợi ở các ga là không đáng kể.

Có tất cả \(\frac{n(n - 1)}{2}\) cách chọn hai ga \(u\) và \(v\). An muốn biết có bao nhiêu cách xây dựng mới một con đường sắt để vua vương quốc LHP hạnh phúc?

Yêu cầu: Bạn hãy viết chương trình cho thông tin mạng lưới xe lửa của vương quốc LHP. Đếm số cách xây dựng mới một con đường xe lửa nối hai ga \(u\) và \(v\) để cho vua vương quốc LHP hạnh phúc.

Dữ liệu vào:

+ Dòng 1 chứa hai số nguyên \(n,\ m\ (2 \leq n \leq 200000,\ 1 \leq m \leq 200000)\)

+ Dòng 2 chứa bốn số nguyên \(s,\ t,\ l,\ k\ (1 \leq s < t \leq n,\ 1 \leq l \leq 10^{9},\ 1 \leq k \leq 10^{15})\).

+ \(m\) dòng tiếp theo, dòng thứ \(i\) chứa 3 số nguyên \(a_{i},\ b_{i},\ c_{i}\ (1 \leq a_{i} < b_{i} \leq n,1 \leq c_{i} \leq 10^{9})\); \((a_{i},b_{i})
eq (a_{i},b_{j})\) với \(i
eq j\).

Kết quả: Ghi một số duy nhất là số cách xây dựng con đường xe lửa để vua LHP hạnh phúc.

Ví dụ:

Ràng buộc:

+ Có 30% số test ứng với 30% số điểm có \(n,\ m \leq 50\).

+ 30% số test ứng với 30% số điểm có \(n,\ m \leq 5000\).

+ 40% số test ứng với 40 % số điểm không có ràng buộc gì thêm.