Dự Án Xây Dựng 2

Một vùng đất có \(N\) thành phố, đánh số từ \(1\) đến \(N\), và \(M\) con đường hai chiều, đánh số từ \(1\) đến \(M\). Con đường thứ \(i\) (\(1 \le i \le M\)) nối trực tiếp thành phố \(A_i\) và thành phố \(B_i\), và đi hết con đường này tốn \(C_i\) phút. Mạng lưới đường ban đầu luôn đảm bảo có thể đi lại giữa hai thành phố bất kỳ (bằng một dãy các con đường).

Hội đồng quy hoạch quyết định xây thêm đúng một con đường mới theo quy tắc sau: chọn hai số nguyên \(u, v\) thoả \(1 \le u < v \le N\), rồi xây một con đường hai chiều mới nối thành phố \(u\) và thành phố \(v\), đi hết con đường này tốn \(L\) phút. Lưu ý rằng có thể chọn \((u, v)\) sao cho giữa \(u\) và \(v\) đã có sẵn một (hoặc nhiều) con đường khác — con đường mới vẫn được xây thêm vào, không thay thế con đường cũ.

Sau khi con đường mới được xây xong, người dân sẽ hài lòng nếu có thể di chuyển từ thành phố \(S\) đến thành phố \(T\) trong tối đa \(K\) phút, bằng cách sử dụng một số con đường bất kỳ (không tính thời gian chuyển tuyến).

Có đúng \(\dfrac{N(N-1)}{2}\) cách chọn cặp \((u, v)\). Hãy đếm xem có bao nhiêu cách chọn \((u, v)\) sao cho sau khi xây con đường mới, người dân hài lòng.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(2 \le N, M \le 200000\)).

• Dòng thứ hai chứa bốn số nguyên \(S, T, L, K\) (\(1 \le S < 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 ba số nguyên \(A_i, B_i, C_i\) (\(1 \le A_i < B_i \le N\), \(1 \le C_i \le 10^9\)) --- mô tả con đường thứ \(i\).

Dữ liệu đảm bảo mạng lưới đường ban đầu luôn liên thông, không có hai con đường nào nối cùng một cặp thành phố.

Ràng buộc:

• Nhóm con 1 (8 điểm): \(L = 1\), \(K = 2\), \(C_i = 1\) với mọi \(i\).

• Nhóm con 2 (16 điểm): \(N \le 50\), \(M \le 50\).

• Nhóm con 3 (29 điểm): \(N \le 3000\), \(M \le 3000\).

• Nhóm con 4 (47 điểm): Không có ràng buộc bổ sung.

Output

In ra một dòng duy nhất chứa một số nguyên — số cách chọn \((u, v)\) khiến người dân hài lòng.

Example 1

Input:

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

Output:

4

Example 2

Input:

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

Output:

3

Example 3

Input:

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

Output:

0

Note

Ở ví dụ thứ nhất, \(S = 6\), \(T = 7\), \(L = 1\), \(K = 2\). Có 4 cách chọn \((u, v)\) để con đường mới nối thẳng một đỉnh cách \(S\) không quá \(0\) phút với một đỉnh cách \(T\) không quá \(1\) phút (hoặc ngược lại), giúp tổng thời gian đi từ \(6\) đến \(7\) không vượt quá \(2\) phút.

Ở ví dụ thứ hai, khoảng cách gốc giữa \(S = 1\) và \(T = 3\) đã là \(2 \le K = 2\), nên mọi cách chọn \((u, v)\) đều khiến người dân hài lòng — đáp số bằng \(\dfrac{3 \times 2}{2} = 3\).

Ở ví dụ thứ ba, với \(L = 10^9\) quá lớn so với \(K = 1\), không có cách chọn \((u,v)\) nào giúp người dân hài lòng, đáp số là \(0\).