Problem
Terdapat bas antara beberapa kampung di wilayah Vasyuki. Memandangkan trafik penumpang di sini tidak begitu besar, bas beroperasi hanya beberapa kali sehari.
Maria Ivanovna perlu pergi dari kampung d ke kampung v secepat mungkin (dia dianggap berada di kampung d pada masa 0).
Input
Mula-mula masukkan nombor N – jumlah bilangan kampung (1 <= N <= 100), maka nombor kampung d dan v, diikuti dengan bilangan perjalanan bas R (0 <= R <= 10000). Berikut adalah penerangan tentang laluan bas. Setiap penerbangan diberikan oleh nombor kampung berlepas, masa berlepas, kampung destinasi dan masa ketibaan (semua masa – adalah integer dari 0 hingga 10000). Jika pada masa t seorang penumpang tiba di beberapa kampung, maka dia boleh meninggalkannya pada bila-bila masa bermula dari t.
Output
Cetak masa minimum apabila Maria Ivanovna boleh berada di kampung v. Jika dia tidak boleh pergi dari d ke v menggunakan laluan bas yang diberikan, cetak -1.
Contoh
| # |
Input |
Output |
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |