Good delivery clerk

Ding dong~
"Who is it?"
"Chicken delivery."
"What? I never ordered chicken... aaargh!"

Inho hands out chicken to customers who never ordered any, so he is a good clerk. He walks along one straight street and gives the customers their chicken house by house.

One day another house joined his delivery list. To bring chicken to the new customer, Inho wants to build exactly one new road. Each of his friends told him about one road that friend is able to build.

Inho calls the chicken shop house 0, then numbers the houses 1, 2, and so on up to house n in order of distance from the shop. The road built by friend j connects house $A_j$ and house $B_j$, and its length is $C_j$. The new house sits on that road.

Inho starts at house 0 and has to deliver chicken to every house from 1 to n and to the new house. He walks under these rules.

• He can change direction only at the two houses that the new road connects.
• When he reaches a dead end he turns back. House 0 and house n are the dead ends.
• If the new road is not fully walked once the deliveries are done, he walks the remaining part of it. The new road therefore gets walked end to end at least once.
• Once every house has its chicken and the new road has been walked in full, he stops where he is.

Find the smallest distance Inho walks when one of the roads his friends offered is built.

The first line contains n, the number of houses Inho already delivered to, and m, the number of friends who can build a road.

The second line contains the distance $L_i$ from house $i-1$ to house $i$, for $i = 1, 2, \dots, n$ in this order.

Each of the next m lines contains $A_j\ B_j\ C_j$, the road that friend j can build. The road connects house $A_j$ and house $B_j$ and its length is $C_j$. $A_j$ and $B_j$ are always different.

$1 \le n, m \le 10000$, $1 \le L_i \le 100$, $1 \le A_j, B_j \le n$, $1 \le C_j \le 100$

Print on one line the smallest distance Inho walks to deliver chicken to every house after one new road is built.

In the first example, building the second road, the road of length 5 between house 3 and house 6, and moving in the order 0, 1, 2, 3, new house, 6, 5, 4 finishes the deliveries after walking 25. Building the first road costs 32.