시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB32266.667%

문제

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?

입력

First line of the input contains two integers N and M, the number of vertices and edges, respectively (1 ≤ N ≤ 104, 0 ≤ M ≤ min(N(N-1)/2, 2 · 104)). Next line contains N integers v0, v1, . . . , vN−1 (1 ≤ vi ≤ 106), weights of respective vertices 0, 1, . . . , N − 1. Each of the next M lines contains three integers fi, ti, and wi (0 ≤ fi, ti < N, 1 ≤ wi ≤ 106), the two vertices connected by the edge and the edge weight, respectively

출력

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

예제 입력 1

2 1
4 5
0 1 20

예제 출력 1

29

예제 입력 2

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

예제 출력 2

33