Road Issue
The road network in Bytrussia is in poor condition: each road is one-way, multiple roads can connect the same pair of cities, and some city pairs may not be connected at all.
To address this, Bytrussia's parliament has enacted a law requiring travelers to pay a tax upon entering each city. The tax amount is fixed for each city and set by the mayor.
This law has upset the trade guilds, prompting them to appeal to the king. Consequently, the king decreed that a traveler entering city X should not be taxed if they have already paid a tax in city Y, provided Y is reachable from X either directly or via other cities (not necessarily those already visited). However, travelers may choose to pay the tax in city X if they wish. Taxes can only be paid upon entering a city.
Bit Bytych Bytogradsky, a merchant from the first guild, needs to travel from Bytrussia's capital M to the major port city C. Naturally, Bit wants to minimize the taxes paid. Note that Bit starts in city M and is not required to pay a tax there at the beginning of the journey.
Given Bytrussia's road map and the entry tax for each city, determine the optimal route for the merchant. It is guaranteed that a path from M to C exists.
Input
The first line of input contains two integers n and m (2 ≤ n ≤ 100000, 1 ≤ m ≤ 500000) - the number of cities and roads in Bytrussia. The second line contains n integers C_i (0 ≤ C_i ≤ 10000) - the entry tax amounts for the cities. The next m lines each contain two integers x_i and y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i), describing the i-th road going from city x_i to city y_i. There may be multiple roads between a pair of cities. For convenience, city M is numbered 1, and city C is numbered n. It is guaranteed that city M can be reached from city C. Numbers in the lines are separated by single spaces.
Output
Output a single number - the minimum sum of taxes that must be paid on the way from M to C.