Problem
Có xe buýt giữa một số làng trong vùng Vasyuki. Do lưu lượng hành khách ở đây không lớn lắm nên xe buýt chỉ chạy vài chuyến mỗi ngày.
Maria Ivanovna cần đi từ làng d đến làng v càng nhanh càng tốt (cô ấy được coi là đang ở làng d tại thời điểm 0).
Đầu vào
Đầu tiên hãy nhập số N – tổng số làng (1 <= N <= 100), sau đó là số làng d và v, theo sau là số chuyến xe buýt R (0 <= R <= 10000). Sau đây là mô tả về các tuyến xe buýt. Mỗi chuyến bay được cung cấp bởi số làng khởi hành, thời gian khởi hành, làng đích và thời gian đến (tất cả thời gian – là số nguyên từ 0 đến 10000). Nếu tại thời điểm t một hành khách đến một ngôi làng nào đó thì anh ta có thể rời đi bất cứ lúc nào bắt đầu từ t.
Đầu ra
In thời gian tối thiểu mà Maria Ivanovna có thể ở trong làng v. Nếu cô ấy không thể đi từ d đến v bằng các tuyến xe buýt đã cho, hãy in -1.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |