有 $N$ 个人，编号为 $0 \le i \le N-1$。每个人的财富值为 $A_i$，保证 $\sum A_i = 0$。

有 $M$ 对人之间可以互相传递财富值，其中第 $i$ 对人 $(p_i ,\ q_i)$ 之间无论传递多少财富值，都要花费 $T_i$ 的代价。

求最少需要花费多少代价才能使所有人的财富值都相同。

输入格式

第一行两个整数 $N \ M \ (2 \le N \le 16,0 \le M \le N*(N-1)/2)$。

下来 $N$ 个整数 $A_i \ (-1000 \le A_i \le 1000)$。

下来 $M$ 行，每行三个整数 $p_i \ q_i \ T_i \ (0 \le p\_i&#44;q\_i < N,0 \le T_i \le 1000)$。保证每对 $p_i、q_i$ 最多出现一次。

输出格式

输出一个整数表示答案，无解输出 Impossible。

样例 #1

样例输入 #1

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

样例输出 #1

30