Omnes Viae Yokohamam Ducunt?

Time limit: 3000 ms. Memory limit: 2048 MB.

"Omnes viae Romam ducunt" is an old Latin proverb meaning "all roads lead to Rome." It is still desirable to have access to the capital from all the regions of a country.

The Kingdom of Kanagawa has a number of cities, including the capital city, Yokohama. The Ministry of Transport of the Kingdom is now planning to construct a highway network that connects all those cities.

There are several candidate highway segments, and each one directly connects two cities. A highway network is a set of segments chosen from the candidates. The network must satisfy the following conditions.

• All the cities must be connected via highway segments in the network, directly or indirectly.
• The number of segments must be minimal to save the budget. In other words, the network must not be redundant, so the path between any two cities is unique.

Access to Yokohama matters most. Because the network has no redundancy, if a natural disaster makes one segment unavailable, some cities become inaccessible from Yokohama.

Each city has a significance value based on its population and economic scale. When a natural disaster hits one segment of a given network, the damage is the sum of the significance values of the cities that become inaccessible from Yokohama. The vulnerability of each candidate segment is also assessed. The risk severity of a segment is the product of its damage and its vulnerability. The total risk severity of a network is the sum of the risk severities of all its segments. Find the minimum total risk severity.

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^5$, $1 \le m \le 3 \times 10^5$), the numbers of cities and candidate segments. The cities are numbered from $1$ to $n$, and Yokohama is city $1$.

The second line contains $n$ integers $p_1, \dots, p_n$, where each $p_i$ ($1 \le p_i \le 1000$) is the significance value of city $i$.

The next $m$ lines describe the candidate segments. Line $j$ contains three integers $u_j$, $v_j$, and $q_j$, meaning the candidate segment between cities $u_j$ and $v_j$ has vulnerability $q_j$ ($1 \le u_j < v_j \le n$, $1 \le q_j \le 10^6$). Each pair $(u_j, v_j)$ appears at most once.

It is guaranteed that a highway network connecting all the cities can be built from some of these segments.

Print the minimum possible total risk severity on one line.