Hệ thống cầu đường của Tèo gồm \(N\) nút giao thông và M con đường liên kết một chiều nối giữa các nút. Con đường thứ i có chiều dài địa lý w và tải trọng giới hạn là \(L\).

Một chiếc xe tải của Tèo có tổng trọng lượng là \(W_{truck}\). Chiếc xe chỉ có thể đi qua con đường nếu tải trọng của con đường lớn hơn hoặc bằng trọng lượng của xe (\(L \ge W_{truck}\)).

Hãy tìm đường đi ngắn nhất từ nút giao \(S\) đến \(T\) cho xe tải của Tèo.

Định dạng đầu vào

• Dòng đầu chứa sáu số nguyên \(N, M, W_{truck}, S, T\) (\(1 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5, 1 \le W_{truck} \le 10^9, 1 \le S, T \le N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(u, v, w, L\) (\(1 \le u, v \le N, 1 \le w, L \le 10^9\)) mô tả con đường một chiều nối u sang v có chiều dài w và giới hạn tải trọng \(L\).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chiều dài ngắn nhất của hành trình. Nếu không thể đi tới, in ra \(-1\).

Ví dụ

Input:

4 4 10 1 4
1 2 2 12
2 3 3 8
1 3 10 15
3 4 4 11

Output:

14

(\(Giải thích ví dụ: Cầu 2 -> 3 có tải trọng 8 < 10 nên xe tải không thể đi qua. Lộ trình khả thi ngắn nhất là 1 -> 3 -> 4 có tổng độ dài 10 + 4 = 14\)).

Ràng buộc