يحتوي السطر الأول على الرقم N (1 & lt؛ = N & lt؛ = 100) ، السطر التالي يحتوي على أرقام N ، حيث يحدد الرقم الأول تكلفة البنزين في المدينة الأولى (كل هذه أعداد صحيحة من النطاق من 0 إلى 100). ثم يأتي الرقم M & ndash؛ عدد الطرق في الدولة ، متبوعًا بوصف للطرق نفسها. كل طريق مُعطاة برقمين - عدد المدن التي يربطها. جميع الطرق ذات اتجاهين (أي ، يمكن قيادتها في اتجاه واحد وفي الاتجاه الآخر) ، لا يوجد دائمًا أكثر من طريق واحد بين مدينتين ، ولا توجد طرق تؤدي من المدينة إلى نفسها.
& nbsp؛
الإخراج
مطلوب لإخراج رقم واحد & ndash؛ التكلفة الإجمالية للمسار ، أو -1 إذا كان من المستحيل الوصول إلى هناك.
& nbsp؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |