Gia đình An sống ở thành phố TB. Hàng ngày, mẹ đi ô tô đến cơ quan làm việc còn An đi bộ đến trường học. Thành phố TB có ~n~ nút giao thông được đánh số từ 1 đến ~n~. Nhà An nằm ở nút giao thông 1, trường của An 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} \le a_{ij}~).

Hôm nay, mẹ và An xuất phát từ nhà lúc 6 giờ. An phải có mặt tại trường lúc 6 giờ 55 phút để kịp vào lớp học lúc 7 giờ. An băn khoăn không biết có thể đến trường đúng giờ hay không, nếu không An 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ố TB. Hãy tìm cách đi để An đế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 đầu vào đảm bảo bài toán có lời giải.

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

Output

• Kết quả ghi ra một số nguyên là thời gian sớm nhất mẹ An đến được cơ quan còn An thì không bị muộn học.

Sample Input 1

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

Sample Output 1

60