Problem Description

Freda, the guardian of the wand, merged four weapons. Then, at the top of the wand, a four-leaf clover slowly grew, and its four leaves shimmered with faint seven-colored light.

Rainbow, the guardian of the holy sword, took out a disk. On the disk, there are $N$ gems, numbered from $0$ to $N-1$. The energy of the $i$-th gem is $A_i$.

If $A_i > 0$, it means the energy of this gem is too high, and it needs to transfer $A_i$ units of energy to other gems. If $A_i < 0$, it means the energy of this gem is too low, and it needs to obtain $-A_i$ units of energy from other gems.

It is guaranteed that $\sum A_i = 0$.

Only when all gems have the same energy can you insert the Clover Wand into the center of the disk and open the passage to the supernatural world.

However, energy can be transferred only between $M$ pairs of gems. For the $i$-th pair, no matter how much energy is transferred, it costs $T_i$.

The explorers want to know the minimum total cost needed to make the energy of all gems equal.

Input Format

The first line contains two integers $N, M$.

The second line contains $N$ integers $A_i$.

The next $M$ lines each contain three integers $p_i, q_i, T_i$, meaning that transferring energy between the gems numbered $p_i$ and $q_i$ costs $T_i$.

The testdata guarantees that each pair $p_i, q_i$ appears at most once.

Output Format

Output one integer representing the answer. If there is no solution, output Impossible.

3 3
50 -20 -30
0 1 10
1 2 20
0 2 100

30

Hint

$2 \le N \le 16$,
$0 \le M \le \dfrac{N(N-1)}{2}$,
$0 \le p_i,q_i < N$,
$-1000 \le A_i \le 1000$,
$0 \le T_i \le 1000$

Translated by ChatGPT 5