Problem
Size ülkenin karayolu ağının bir açıklaması verilir. Göreviniz – A ve B şehirleri arasındaki en kısa yolun uzunluğunu bulun.
Girdi
Yol ağı, giriş dosyasında şu şekilde verilmiştir: ilk satır, N ve K sayılarını içerir (1<=N<=100000, 0<=K<=300000), burada K – yol sayısı Aşağıdaki K satırlarının her biri, iki yönlü bir yolun açıklamasını içerir. üç tamsayı ai, bi ve li (1aibiN, 1li106). Bu, ai şehrinden bi şehrine giden li uzunluğunda bir yol olduğu anlamına gelir. Son satır iki sayı A ve B – en kısa mesafenin hesaplanması gereken şehir sayısı (1<=A,B<=N )
Künye
Tek sayıyı çıkarmalısınız – gerekli şehirler arasındaki mesafe. A şehrinden B şehrine karayoluyla ulaşmak imkansızsa, –1'i yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |