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 i đến nút j 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 j đến nút i. Nếu từ nút i đến nút j có đường đi thì thời gian đi bộ từ nút i đến nút j hết a_ij phút, còn đi ô tô hết b_ij phút (0 < b_ij ≤ a_ij).

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 nhập:

- Dòng đầu ghi ba số nguyên dương N, M, K (3 ≤ N ≤ 10.000, M ≤ 10⁵, 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.

- Trong M dòng tiếp theo, mỗi dòng chứa 4 số nguyên dương i, j, a_ij, b_ij (1 ≤ i, j ≤ N, b_ij ≤ a_ij ≤ 60) mô tả thông tin đường đi một chiều từ i đến j.

(Hai số liên tiếp trên một dòng cách nhau một dấu cách, dữ liệu cho đảm bảo luôn có nghiệm)

Dữ liệu xuất:

- Là số nguyên xác định 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.