देश में N शहर हैं, जिनमें से कुछ सड़कों से जुड़े हुए हैं। एक सड़क पर गाड़ी चलाने के लिए पेट्रोल का एक टैंक लगता है। हर शहर में पेट्रोल के एक टैंक की कीमत अलग होती है। जितना संभव हो उतना कम पैसा खर्च करके आपको पहले शहर से एनवें शहर तक जाने की जरूरत है। आप भविष्य में इस्तेमाल के लिए पेट्रोल नहीं खरीद सकते।
पहली पंक्ति में संख्या N (1≤N≤100) है, अगली पंक्ति में N संख्याएँ हैं, जिनमें से i-th, i-वें शहर में गैसोलीन की लागत निर्दिष्ट करता है (ये 0 से 100 तक के पूर्णांक हैं ). फिर नंबर आता है M – देश में सड़कों की संख्या, उसके बाद स्वयं सड़कों का विवरण। प्रत्येक सड़क को दो संख्याओं द्वारा दिया जाता है - यह कनेक्ट होने वाले शहरों की संख्या। सभी सड़कें दो-तरफ़ा हैं (अर्थात, उन्हें एक दिशा और दूसरी दिशा दोनों में चलाया जा सकता है), दो शहरों के बीच हमेशा एक से अधिक सड़कें नहीं होती हैं, शहर से खुद की ओर जाने वाली सड़कें नहीं होती हैं।
आउटपुट
एक संख्या को आउटपुट करने के लिए आवश्यक है – मार्ग की कुल लागत या -1 अगर वहाँ जाना असंभव है।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
5
3 6 1 7 6
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
3 |