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}\) (\(0 < b_{ij} \leq a_{ij}\)) 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ờ (tổng thời gian di chuyển của Tuấn không quá \(59\) phút) còn mẹ đến cơ quan làm việc sớm nhất.

Input

• 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 \(i, j, a_{ij}, b_{ij}\) (\(1 \leq i, j \leq N, b_{ij} \leq a_{ij} \leq 60\)) mô tả thông tin đường đi một chiều từ \(i\) đến \(j\).

Output

• Đư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 mà vẫn đảm bảo Tuấn đến trường không bị muộn học.

Example

5 6 3
1 4 60 40
1 2 60 30
2 3 60 30
4 5 30 15
4 3 19 10
3 5 20 10

55

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 100\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 10^5, M \leq 10^5\).