Gia đình Tuấn sống ở thành phố XYZ. Hàng ngày, mẹ đi ô tô đến cơ quan làm việc còn Tuấn đi bộ đến trường học. Thành phố XYZ có N nút giao thông được đánh số từ 1 đến N. Nhà Tuấn nằm ở nút giao thông 1, trường của Tuấn nằm ở nút giao thông K, cơ quan của mẹ nằm ở nút giao thông N. Từ nút 𝑖 đến nút 𝑗 có không quá một đường đi một chiều, tất nhiên, có thể có đường đi một chiều khác đi từ nút 𝑗 đến nút 𝑖. Nếu từ nút 𝑖 đến nút 𝑗 có đường đi thì thời gian đi bộ từ nút 𝑖 đến nút 𝑗 hết 𝑎_𝑖𝑗 phút, còn đi ô tô hết 𝑏_𝑖𝑗(0 < 𝑏_𝑖𝑗 ≤ 𝑎_𝑖𝑗) phút.

Hôm nay, mẹ và Tuấn xuất phát từ nhà lúc 7 giờ. Tuấn phải có mặt tại trường lúc 7 giờ 59 phút để kịp vào lớp học lúc 8 giờ. Tuấn băn khoăn không biết có thể đến trường đúng giờ hay không, nếu không Tuấn sẽ phải nhờ mẹ đưa đi từ nhà đến một nút giao thông nào đó.

Yêu cầu: Cho biết thông tin về các đường đi của thành phố XYZ. Hãy tìm cách đi để Tuấn đến trường không bị muộn giờ còn mẹ đến cơ quan làm việc sớm nhất.

Dữ liệu:

- Dòng đầu ghi ba số nguyên dương N, M, K (1 < K < N), trong đó N là số nút giao thông, M là số đường đi một chiều, K là nút giao thông - trường của Tuấn.
- M dòng tiếp theo, mỗi dòng chứa 4 số nguyên dương 𝑖,𝑗, 𝑎_𝑖𝑗, 𝑏_𝑖𝑗 (1 ≤ 𝑖,𝑗 ≤ 𝑁, 𝑏_𝑖𝑗 ≤ 𝑎_𝑖𝑗 ≤ 60) mô tả thông tin đường đi một chiều từ i đến j.

Kết quả:

Đưa ra một dòng chứa một số nguyên là thời gian sớm nhất mẹ Tuấn đến được cơ quan còn Tuấn thì không bị muộn học