Petrol Stations#1388
There are cities in the country, some of which are connected by roads. To travel along one road, one tank of gasoline is required. In each city, the cost of a full tank of gasoline is different. Your task is to get from the first city to the -th city with minimum expenses.
The first line contains the number of cities (1 \leq n \leq 100).
The second line contains integers, where the -th number represents the cost of gasoline in the -th city (all numbers are integers from to ).
The third line contains the number of roads in the country, followed by the description of the roads.
Each road is represented by two integers — the numbers of the cities it connects. All roads are bidirectional (that is, you can travel in both directions), there is at most one road between any two cities, and there are no roads that lead from a city to itself.
Print a single integer — the minimum cost of the route, or if it is impossible to reach the -th city.
Example 1
Example 2