Balancing Gem Energies via Minimum Spanning Tree

Wizardess Freda and Sword Guardian Rainbow are faced with an extraordinary challenge. Rainbow reveals a circular disk embedded with N gems numbered from 0 to N-1, where each gem i has an energy value A_i. If A_i > 0, the gem has surplus energy which needs to be transferred to other gems; if A_i < 0, the gem needs to receive -A_i energy from others. It is guaranteed that \(\sum_{i=0}^{N-1} A_i = 0\).

The four‐leaf clover wand can only activate the portal to the supernatural realm when all gems have the same energy, achieved by transferring energy along allowed pairs of gems. However, only M pairs of gems can transfer energy between each other. For the i-th allowed pair, any amount of energy transferred between the two gems costs \(T_i\) (in other words, if this pair is used at least once, the cost \(T_i\) is incurred).

Determine the minimum total cost required to make all gem energies equal. Energy can be transferred arbitrarily along the chosen allowed pairs. Note that if it is impossible to connect all gems (i.e. make them capable of energy exchange) using the allowed pairs, output -1. Hint: In order to equalize energy among all gems, the chosen pairs (edges) must connect all the gems, forming a spanning tree. Therefore, the problem reduces to finding a minimum spanning tree (MST) in the given graph. If the graph is disconnected, it is impossible to balance the energy.

inputFormat

The input begins with a line containing two integers N and M separated by a space, representing the number of gems and the number of allowed pairs, respectively.

The next line contains N integers \(A_0, A_1, \dots, A_{N-1}\) separated by spaces, representing the energy of each gem. It is guaranteed that \(\sum_{i=0}^{N-1} A_i = 0\).

The following M lines each contain three integers u, v and T, meaning that energy can be transferred between gem u and gem v (0-indexed) with a cost of T (if that pair is used at least once).

outputFormat

Output a single integer: the minimum total cost required to equalize the energy of all gems by selecting a subset of the allowed pairs. If it is impossible (i.e. the allowed pairs cannot connect all gems), output -1.

sample

3 3
3 -1 -2
0 1 5
1 2 1
0 2 10

6