Problem H
TomTom Cruise

You intend to take a trip from your base to Ganymede. You have a spaceship which you will use for the whole trip. It will take some fuel to get there, some fuel to traverse part of the moon, and some fuel to get back to the base.

There are some points on Ganymede you can visit. The map of Ganymede is given as a graph where the weight of each vertex is equal to the amount of fuel it will take to traverse between the corresponding point and your base. The weight of each edge equals to the amount of fuel it will take to traverse between vertices which are connected by the edge, in either direction. In order for your trip to be reasonable, you do not want to visit any edge or any vertex twice. However, you have to traverse at least one edge.

What is the least amount of fuel you will need to accomplish such a trip?

Input

First line of the input contains two integers $N$ and $M$, the number of vertices and edges, respectively ($1 \le N \le 10^4$, $0 \le M \le \min (\binom {N}{2}, 2 \cdot 10^4$).

The next line contains $N$ integers $v_0, v_1, \dots , v_{N-1}$ ($1 \le v_ i \le 10^6$), weights of respective vertices $0, 1, \dots , N - 1$.

Each of the next $M$ lines contains three integers $f_ i$ , $t_ i$ , and $w_ i$ ($0 \le f_ i, ti < N$, $1 \le wi \le 10^6$), the two vertices connected by the edge and the edge weight, respectively.

Output

Output the minimum amount of fuel you have to spend on your trip.

2 1
4 5
0 1 20

29

3 3
10 40 20
0 1 1
0 2 4
2 1 2

33