题目描述

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

圣剑护法rainbow取出了一个圆盘，圆盘上镶嵌着 $\red {N}$ 颗宝石，编号为$\red {0\sim N-1}$。

第 $\red {i}$ 颗宝石的能量是 $\red {A_i}$。

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

保证$\red {∑A _i =0}$。

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

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

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

输入格式

第一行两个整数$\red {N、M}$。

第二行 $\red {N }$个整数$\red {A_i}$。

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

数据保证每对 $\red {p _i}$ 、$\red {q_i}$ 最多出现一次。

输出格式

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

样例

输入样例

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

输出样例

30

提示

$\red {2≤N≤16}$,

$\red {0≤M≤N\times (N−1)/2}$,

$\red {0≤p _i ,q _i <N}$,

$\red {−1000≤A _i ≤1000}$,

$\red {0≤T_i ≤1000}$