Trong chuyến tham quan rừng Cúc Phương bằng xe gắn máy, Thành cần đi từ điểm \(s\) đến điểm \(t\) để đổ xăng. Mạng lưới giao thông có thể mô tả là bản đồ gồm \(n\) nút giao thông và \(m\) con đường 2 chiều. Mỗi con đường hai chiều nối 2 nút giao thông được cho bởi độ dài đoạn đường, lượng xăng cần tiêu thụ với xe gắn máy. Do chất lượng của các đoạn đường khác nhau nên lượng xăng cần thiết để đi trên các đoạn đường có thể không tỉ lệ thuận với độ dài.

Yêu cầu: Với lượng xăng còn lại trong bình xăng là \(p\), tìm đường đi ngắn nhất từ điểm \(s\) đến điểm \(t\).

Dữ liệu vào:

+ Dòng đầu là các số \(n,m,p\ (n,m \leq 1000,p \leq 1000)\);

+ Dòng thứ 2 chứa 2 số \(s,\ t\) \((1 \leq s,\ t \leq n)\);

+ \(m\) dòng tiếp theo, mỗi dòng chứa 4 số \(u,\ v,\ x,\ y\) cho biết có đoạn đường nối giữa hai nút \(u\) và \(v\) có độ dài là \(x\) và lượng xăng cần thiết để đi qua là \(y\) \((1 \leq u,v \leq n;x,\ y \leq 1000)\)

Kết quả:

+ Ghi một số duy nhất là kết quả bài toán, nếu không có đường đi thoả mãn thì ghi ra số \(- 1\).

Ví dụ:

Ràng buộc:

+ 50% số test có \(n \leq 100\), dữ liệu đảm bảo lượng xăng luôn dư thừa để đi từ \(s\) đến \(t\).

+ 50% số test không có thêm ràng buộc khác.