Problem
Vasyuki bölgesindeki bazı köyler arasında otobüs seferleri var. Buradaki yolcu trafiği çok fazla olmadığı için otobüsler günde sadece birkaç sefer yapıyor.
Maria Ivanovna'nın d köyünden v köyüne olabildiğince çabuk gitmesi gerekiyor (0 zamanında d köyünde olduğu kabul ediliyor).
Giriş
Önce N sayısını girin – toplam köy sayısı (1 <= N <= 100), sonra köy numaraları d ve v, ardından otobüs yolculuklarının sayısı R (0 <= R <= 10000). Aşağıda otobüs güzergahlarının açıklamaları bulunmaktadır. Her uçuş, kalkış köy numarası, kalkış saati, varış köyü ve varış saati ile verilir (tüm zamanlar - 0 ile 10000 arasında tam sayılardır). t zamanında bir yolcu bir köye varırsa, t'den başlayarak herhangi bir zamanda orayı terk edebilir.
Çıktı
Maria Ivanovna'nın köyde olabileceği minimum süreyi yazdırın v. Verilen otobüs güzergahlarını kullanarak d'den v'ye gidemezse, -1 yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |