Petrol Stations
There are 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 -th one, spending the minimum possible amount of money.
Input
Starts with the number of cities, followed by numbers, -th of which gives the cost of gasoline in the -th city (all numbers are integers in the range from to ). Then the number 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 if it is impossible to reach the -th city.