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\).

Ràng buộc

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).