توجد مدن N في البلد ، بعضها متصل بالطرق. يتطلب الأمر خزانًا واحدًا من البنزين للقيادة على طريق واحد. في كل مدينة ، تختلف تكلفة خزان البنزين. تحتاج إلى الانتقال من المدينة الأولى إلى المدينة الأولى ، وإنفاق أقل قدر ممكن من المال. لا يمكنك شراء البنزين للاستخدام في المستقبل.
& nbsp؛
إدخال
يحتوي السطر الأول على الرقم N (1 & le؛ N & le؛ 100) ، السطر التالي يحتوي على أرقام N ، والتي تحدد i-th منها تكلفة البنزين في المدينة الأولى (هذه أعداد صحيحة من 0 إلى 100 ). ثم يأتي الرقم M & ndash؛ عدد الطرق في الدولة ، متبوعًا بوصف للطرق نفسها. كل طريق مُعطاة برقمين - عدد المدن التي يربطها. جميع الطرق ذات اتجاهين (أي ، يمكن قيادتها في اتجاه واحد وفي الاتجاه الآخر) ، لا يوجد دائمًا أكثر من طريق واحد بين مدينتين ، ولا توجد طرق تؤدي من المدينة إلى نفسها.
& nbsp؛
الإخراج
مطلوب لإخراج رقم واحد & ndash؛ التكلفة الإجمالية للمسار أو -1 إذا كان من المستحيل الوصول إلى هناك.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
5
3 6 1 7 6 & nbsp؛
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
|
3 |