Routing a Marathon Race

As a member of the Ibaraki Committee of Physical Competitions, you plan the route of a marathon event held in the City of Tsukuba. A great number of runners, from beginners to experts, take part.

You have a city map that lists every street segment suited for the event and every junction on those segments. The race starts at the junction in front of Tsukuba High and ends at the junction in front of City Hall. Both are marked on the map.

To avoid congestion and confusion of runners of divergent skills, the route does not visit the same junction twice. A street segment can be run in either direction, but it goes into the route at most once. The event is about recreation and the health of citizens, so time records do not matter and you can decide the distance of the route freely.

Personnel have to be stationed at every junction on the route. Junctions connected directly by a street segment to a junction on the route also need personnel, so that casual traffic does not interfere with the race. Junction $k$ needs $c_k$ personnel, and that number is the same whether the junction is on the route or next to a junction on the route. Different junctions need different numbers depending on their sizes and shapes, and the map gives those numbers. No junction is staffed twice.

The municipal authorities want to reduce the personnel expense of events of this kind. Write a program that plans a route requiring the fewest personnel and prints that number.

The input consists of a single test case representing a summary city map, formatted as follows.

n m
c1
.
.
.
cn
i1 j1
.
.
.
im jm

The first line has two positive integers $n$ and $m$. Here $n$ is the number of junctions in the map ($2 \le n \le 40$), and $m$ is the number of street segments connecting adjacent junctions. Junctions are identified by integers $1$ through $n$.

Then come $n$ lines giving the numbers of personnel required. The $k$-th of them, an integer $c_k$, is the number of personnel required for junction $k$ ($1 \le c_k \le 100$).

The remaining $m$ lines list street segments between junctions. The two integers $i_k$ and $j_k$ on each line represent a segment connecting junctions $i_k$ and $j_k$ ($i_k \ne j_k$). At most one street segment connects the same pair of junctions.

The race starts at junction $1$ and the goal is junction $n$. At least one route connects the start and the goal.

Print one integer, the minimum possible number of personnel required.

The figure shows the lowest-cost route for the first example input. The arrows indicate the route and the circles painted gray are junctions requiring personnel. The minimum number of required personnel is 17 in that case.