Ülkede, bazıları karayoluyla birbirine bağlı N şehir vardır. Bir yolda sürmek için bir depo benzin gerekir. Ayrıca, benzin deposuyla aynı miktarda yakıt alan bir benzin bidonunuz var.
Her şehirde bir depo benzinin maliyeti farklıdır. Mümkün olduğunca az para harcayarak ilk şehirden N. şehire gitmeniz gerekiyor.
Her şehirde depoyu doldurabilir, depoyu ve bidonu doldurabilir veya bidondan depoya benzin dökebilirsiniz. Bu, daha ucuz olduğu şehirlerde benzin satın alarak paradan tasarruf etmenizi sağlar, ancak teneke kutu yalnızca bir depoyu doldurmak için yeterlidir!
Giriş
İlk satır N sayısını (1<=N<=100), sonraki satırda i'incisi i'inci şehirdeki benzinin maliyetini belirleyen N sayıları içerir (tüm bunlar 0 ila 100 aralığı). Sonra M sayısı gelir – ülkedeki yolların sayısı, ardından yolların açıklamaları. Her yol iki sayı ile verilir – bağlandığı şehirlerin sayısı. Tüm yollar çift yönlüdür (yani hem bir yönde hem de diğer yönde sürülebilirler), iki şehir arasında her zaman birden fazla yol yoktur, şehirden kendisine giden yollar yoktur.
Çıktı
Tek bir sayı çıktısı almak için gereklidir – rotanın toplam maliyeti veya oraya ulaşmak imkansızsa -1.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |