# Dijkstra algorithm

# 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** (**1** ≤ **n** ≤ **100**) 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 (it's 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.

4 1 10 2 15 4 1 2 1 3 4 2 4 3

3

4 1 10 2 15 0

-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