REF: Chuyên tin 2010

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 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.

Hôm nay, mẹ và Tuấn xuất phát từ nhà lúc ~7~ giờ. Anh ấy 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 đó.

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.

Input

Dòng thứ nhất chứa ba số nguyên dương ~N, M, K, (3 \le N \le 10000; M \le 10^5 ; 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 bốn số nguyên dương ~i, j, a_{ij} , b_{ij} ,(1 \le i, j \le N, 0<b_{ij} \le a_{ij} \le 60)~ mô tả thông tin đường đi một chiều từ ~i~ đến ~j~.

Chú ý: dữ liệu bảo đảm luôn có nghiệm

Output

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

Samples

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

55