作为 ICPC（茨城体育竞赛委员会）的一员，你负责规划在筑波市举办的马拉松比赛路线。预计将有大量从初学者到专家级别的选手参加。

你手头有一份城市地图，列出了所有适合比赛的街道段以及它们连接的所有路口。比赛起点位于筑波高中门前的路口，终点位于市政厅门前的路口，这两个路口都在地图上标出。

为了避免不同水平选手的拥堵和混乱，路线不应经过同一个路口两次。因此，尽管街道段可以双向使用，但每条街道段在路线中最多只能包含一次。由于本次活动的主要目的是娱乐和促进市民健康，时间记录并不重要，路线距离可以任意决定。

路线上的每个路口都需要部署一定数量的工作人员。与路线上的路口相邻的路口（即通过街道段直接与路线上的路口相连的路口）也需要安排工作人员，以防止日常交通干扰比赛。当一个路口在路线上时，以及当它与路线上的路口相邻时，所需的工作人员数量相同，但不同的路口根据其大小和形状需要不同数量的工作人员，这些信息也在地图上标明。

市政当局渴望降低包括人员费用在内的此类活动的成本。你的任务是编写一个程序，规划一条所需工作人员总数最少的路线，并输出该数量。

输入格式

输入包含一个代表城市地图摘要的测试用例，格式如下：

$n$ $m$ $c_1$ $\vdots$ $c_n$ $i_1$ $j_1$ $\vdots$ $i_m$ $j_m$

测试用例的第一行包含两个正整数 $n$ 和 $m$。其中，$n$ 表示地图中的路口数量（$2 \le n \le 40$），$m$ 是连接相邻路口的街道段数量。路口由 $1$ 到 $n$ 的整数标识。

接下来是 $n$ 行，表示所需的工作人员数量。其中第 $k$ 行是一个整数 $c_k$（$1 \le c_k \le 100$），表示路口 $k$ 所需的工作人员数量。

剩下的 $m$ 行列出了路口之间的街道段。每行包含两个整数 $i_k$ 和 $j_k$，表示连接路口 $i_k$ 和 $j_k$ 的街道段（$i_k \neq j_k$）。连接同一对路口的街道段最多只有一条。

比赛从路口 $1$ 开始，终点为路口 $n$。保证至少存在一条连接起点和终点的路线。

输出格式

输出一个整数，表示所需的最少工作人员总数。

图 I.1. 样例输入 1 的最低成本路线

图 I.1 展示了样例输入 1 的最低成本路线。箭头指示了路线，灰色圆圈表示需要分配工作人员的路口。在这种情况下，所需的最少工作人员数量为 17。

样例

样例输入 1

6 6
3
1
9
4
3
6
1 2
1 4
2 6
5 4
6 5
3 2

样例输出 1

17