小朋友有n个玩具和m条绳子，每条绳子连着两个玩具，每两个玩具之间最多连一条绳子。小朋友要取某个玩具，就要消耗能量，这个能量就是跟这个玩具直接相连的其他玩具的能量值（已经被取走的玩具就不算相连了）。如下面样例1,4个玩具和3条绳子，每个玩具的能量值分别为10,20,30,40，其中1和4相连，1和2相连，2和3相连。小朋友如果要取光所有玩具，可以先取玩具3，这样就要消耗跟3直接相连的2的能量，花费20能量；然后取玩具2，这样就要消耗玩具1的能量值，花费10能量；然后取玩具4，也花费10；最后取玩具1，因为没有玩具与之相连了，不用花费能量。所以总共需要花费20+10+10+0能量，这也是取走所有玩具花费的最少能量。

给你n个玩具和m条绳子，每个玩具的能量值（n个数字）以及玩具间相连的情况（m行，每行两个数字a,b，表示玩具a与玩具b相连），问花费最少能量是多少？

玩具编号为1到n，1<=n<=1000, 0<=m<=2000, 能量值为[0, 100000]之间的整数。

输出最少花费。

input

4 4
100 100 100 100
1 2
2 3
2 4
3 4

output

400

input

7 10
40 10 20 10 20 80 40
1 5
4 7
4 5
5 2
5 7
6 4
1 6
1 3
4 3
1 4

output

160