题目描述

魔杖护法 Freda 融合了四件武器，于是魔杖顶端缓缓地生出了一棵四叶草，四片叶子幻发着淡淡的七色光。

圣剑护法 rainbow 取出了一个圆盘，圆盘上镶嵌着 $N$颗宝石，编号为 0∼$N$−1。

第 $i$ 颗宝石的能量是 $A_i$。

如果 $A+i$>0，表示这颗宝石能量过高，需要把$A_i$ 的能量传给其它宝石；如果 $A_i$<0，表示这颗宝石的能量过低，需要从其它宝石处获取 −$A_i$ 的能量。

保证$\sum A_i$=0。

只有当所有宝石的能量均相同时，把四叶草魔杖插入圆盘中央，才能开启超自然之界的通道。

不过，只有 $M$对宝石之间可以互相传递能量，其中第 $i$ 对宝石之间无论传递多少能量，都要花费 $T_i$ 的代价。

探险队员们想知道，最少需要花费多少代价才能使所有宝石的能量都相同？

输入格式

第一行两个整数$N、M$。

第二行 $N$个整数 $A_i$。

接下来$M$行每行三个整数$p_i,q_i,T_i$，表示在编号为 $p_i$ 和 $q_i$ 的宝石之间传递能量需要花费$T_i$的代价。

数据保证每对$p_i、q_i$最多出现一次。

输出格式

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

样例

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

30

数据范围

$2≤N≤16,0≤M≤N∗(N−1)/2, 0≤p_i,q_i<N,−1000≤A_i≤1000,0≤T_i≤1000$

来源

• 算法竞赛进阶指南