국가에는 N개의 도시가 있으며 그 중 일부는 도로로 연결되어 있습니다. 한 도로를 주행하려면 휘발유 한 탱크가 필요합니다. 각 도시에서 휘발유 탱크의 비용은 다릅니다. 가능한 한 적은 비용으로 첫 번째 도시에서 N 번째 도시로 이동해야 합니다. 나중에 사용하기 위해 휘발유를 살 수 없습니다.
첫 번째 줄에는 숫자 N(1≤N≤100)이 포함되고, 다음 줄에는 N개의 숫자가 포함되며, 그 중 i번째는 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 |