توجد حافلات بين بعض القرى في منطقة فاسيوكي. نظرًا لأن حركة الركاب هنا ليست كبيرة جدًا ، تعمل الحافلات بضع مرات فقط في اليوم.
تحتاج ماريا إيفانوفنا إلى الانتقال من القرية d إلى القرية v بأسرع ما يمكن (تعتبر أنها في القرية d في الوقت 0).
& nbsp؛
إدخال
أدخل الرقم أولاً N & ndash؛ إجمالي عدد القرى (1 & lt ؛ = N & lt ؛ = 100) ، & nbsp ؛ ثم أرقام القرية d و v ، & nbsp؛ متبوعًا بعدد رحلات الحافلات R (0 & lt ؛ = R & lt ؛ = 10000). فيما يلي وصف لخطوط الحافلات. يتم إعطاء كل رحلة من خلال رقم قرية المغادرة ووقت المغادرة وقرية الوجهة ووقت الوصول (جميع الأوقات - هي أعداد صحيحة من 0 إلى 10000). إذا وصل أحد الركاب في وقت ما إلى قرية ما ، فيمكنه مغادرتها في أي وقت بدءًا من t.
& nbsp؛
الإخراج
اطبع الحد الأدنى للوقت الذي يمكن أن تكون فيه Maria Ivanovna في القرية v. إذا لم تستطع الانتقال من d إلى v باستخدام مسارات الحافلات المحددة ، اطبع -1.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |