e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

ADA University - February 3 - Dijkstra

Petrol Stations

There are n cities, some of which are connected by roads. In order to drive along one road you need one tank of gasoline. In each city the petrol tank has a different cost. You need to get out of the first city and reach the n-th one, spending the minimum possible amount of money.

Input

Starts with the number n (1n100) of cities, followed by n numbers, i-th of which gives the cost of gasoline in the i-th city (all numbers are integers in the range from 0 to 100). Then the number m of roads in the country is given. It is followed by the description of roads. Each road is defined by two numbers - the numbers of cities it connects. All roads are two-way (its possible to travel in both directions). There is always no more than one road between the two cities. There is no road from the city to itself.

Output

Print the total cost of the route, or -1 if it is impossible to reach the n-th city.

prb1388.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
1 10 2 15
4
1 2 1 3 4 2 4 3
Output example #1
3
Input example #2
4
1 10 2 15
0
Output example #2
-1

Example description: In the first example of an optimal solution - from the 1 st of the city to go to third, and then in the 4 th. Fuel will have to buy at 1 and 3 cities