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

Hôm nay, mẹ và Tèo xuất phát từ nhà lúc 7 giờ. Tèo 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ờ. Mẹ cũng có việc nên muốn đến cơ quan thật sớm. Tèo băn khoăn không biết có thể đến trường đúng giờ hay không, nếu không Tèo 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ố X.

Yêu cầu: Hãy tìm cách đi để mẹ đến cơ quan làm việc sớm nhất sao cho Tèo đến trường không bị muộn học.

Dữ liệu

• Dòng 1: ba số nguyên dương ~N, M, K~ (~1 < K \le N~), trong đó ~N~ là số nút giao thông của thành phố, ~M~ là số đường đi một chiều, ~K~ là nút giao thông của trường Tèo.
• ~M~ dòng tiếp theo, mỗi dòng ghi 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~.

Dữ liệu đầu vào đảm bảo luôn có cách để Tèo đến trường không bị muộn.

Kết quả

Ghi một số nguyên ~t~ là thời gian sớm nhất (tính bằng phút) mẹ Tèo đến được cơ quan sao cho Tèo vẫn không bị muộn học.

Trong các test thực tế của đề, nếu không có cách đi nào thỏa mãn thì kết quả được ghi là 1000000000.

Ví dụ

SCHOOL.INP

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

SCHOOL.OUT

55

Giải thích: Mẹ chở Tèo đi ô tô từ nhà (nút 1) đến nút 4 mất thời gian là 40 phút, sau đó Tèo đi bộ từ nút 4 đến trường (nút 3) mất 19 phút còn mẹ đi ô tô từ nút 4 đến cơ quan (nút 5) mất 15 phút. Tổng thời gian Tèo đến trường là 59 phút nên vẫn kịp. Còn tổng thời gian mẹ đi từ nhà đến cơ quan là 55 phút chính là thời gian tối ưu tìm được.

Giới hạn

• Có 50% số test tương ứng với 50% số điểm của bài có ~2 \le N \le 100~.
• Có 50% số test còn lại ứng với 50% số điểm của bài có ~100 < N, M \le 10^5~.