Có \(n\) ga xe lửa ở vương quốc LHP, các ga được đánh số 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 \le i \le 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 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 \le u \lt v \le n\). Xây dựng 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ột con đường sắt để vua vương quốc LHP hạnh phúc?

Yêu cầu:

• 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 \le n \le 200000, 1 \le m \le 200000)\)
• Dòng \(2\) chứa bốn số nguyên \(s, t, l, k\) \((1 \le s \lt t \le n, 1 \le l \le 10^9, 1 \le k \le 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 \le a_i \lt b_i \le n, 1 \le c_i \le 10^9)\)
  • \((a_i, b_i) \neq (a_j, b_j)\) với \(i \neq j\)

Kết quả:

• In ra một số nguyên duy nhất là số cách xây dựng con đường xe lửa để vua LHP hạnh phúc.

Input 1

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

Output 1

3

Ràng buộc:

• Có 30% số test ứng với 30% số điểm có \(n, m \le 50\)
• 30% số test ứng với 30% số điểm có \(n, m \le 5000\)
• 40% số test ứng với 40% số điểm không có ràng buộc gì thêm