题目描述

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

圣剑护法 rainbow 取出了一个圆盘，圆盘上镶嵌着 $N$ 颗宝石，编号为 $0 \sim 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

样例解释

输入

$N=3, M=3$ $A = [50, -20, -30]$，总和为 0。 边： 0-1 代价 10 1-2 代价 20 0-2 代价 100

目标

使三颗宝石能量相同。因为总和为 0，所以最终每颗宝石能量应为 0。

初始能量：宝石0 多 50，宝石1 少 20，宝石2 少 30。

需要将宝石0 的能量传递给宝石1 和宝石2。

传递方案

最优方案：

• 宝石0 传递 20 能量给宝石1，代价 = 20 × 10 = 200
• 宝石0 传递 30 能量给宝石2，代价 = 30 × 100 = 3000 总代价 3200，很大。

但我们可以通过中间节点传递：

• 宝石0 传递 50 能量给宝石1，代价 = 50 × 10 = 500
• 宝石1 传递 20 能量给宝石2（因为宝石1 需要 -20，即需要接收 20，但这里它先接收 50，再转出 20），代价 = 20 × 20 = 400 总代价 900。

或者：

• 宝石0 传递 30 能量给宝石2，代价 = 30 × 100 = 3000
• 宝石0 传递 20 能量给宝石1，代价 = 20 × 10 = 200 总 3200。

另一种：宝石0 传递 50 给宝石1（代价 500），宝石1 传递 30 给宝石2（代价 30×20=600），总 1100。

但样例输出是 30，说明我们理解有误。

题目说“无论传递多少能量，都要花费 $T_i$ 的代价”，意思是只要在这两个宝石之间传递能量，就花费 $T_i$ 的固定代价，与传递的能量大小无关？还是说每传递一单位能量花费 $T_i$？

从样例看，如果每单位能量花费 $T_i$，那么最小代价方案应该是：宝石0→宝石1 传递 20（代价 200），宝石0→宝石2 传递 30（代价 3000），总 3200，不是 30。

如果固定代价，那么只要在 0-1 之间传一次，代价 10；在 1-2 之间传一次，代价 20，总 30。但这样如何使能量平衡？

传递过程：宝石0 传能量给宝石1，假设传递的量是 x，则宝石0 减少 x，宝石1 增加 x。同时宝石1 传能量给宝石2，传递量 y，宝石1 减少 y，宝石2 增加 y。

最终能量： 宝石0: 50 - x 宝石1: -20 + x - y 宝石2: -30 + y

要求三者相等，设为 v。 则： 50 - x = v -20 + x - y = v -30 + y = v

解方程： 从第一式：x = 50 - v 从第三式：y = v + 30 代入第二式：-20 + (50 - v) - (v + 30) = v => -20 + 50 - v - v - 30 = v => 0 - 2v = v => 3v = 0 => v = 0 则 x = 50, y = 30。

传递方案：宝石0 传 50 给宝石1（固定代价 10），宝石1 传 30 给宝石2（固定代价 20），总代价 30。

这样理解：每对宝石之间传递能量，无论传递多少，都只需支付一次固定代价 $T_i$。

所以问题转化为：选择一些边，使得通过这些边可以调整能量，使所有点能量变为平均值（0），且总代价最小。

数据范围

• $2 \le N \le 16$
• $0 \le M \le N(N-1)/2$
• $-1000 \le A_i \le 1000$
• $0 \le T_i \le 1000$

算法分析

这是一个最小代价传递问题，可以转化为最小生成树或状态压缩动态规划。

由于 $N \le 16$，可以使用状态压缩 DP。

关键观察

如果选择了一些边构成一个连通子图，那么这个连通子图内的能量可以自由传递（因为传递没有容量限制，且代价固定），最终使子图内所有点的能量相等（即平均值）。代价就是这个子图内所有边的代价和。

我们的目标是将所有点分成若干个连通块，每个连通块内能量可以平衡（即块内 $A_i$ 之和为 0），然后为每个连通块选择一棵生成树（用于传递能量），总代价为所有生成树的边权和的最小值。

因为如果块内能量和不为 0，那么无法通过内部传递使所有点能量相等（因为总和不为 0，无法达到平均值）。

问题转化

将点集划分成若干个连通块，每个连通块满足：

1. 块内点集的 $A$ 之和为 0。
2. 块内点连通（通过选择的边）。
3. 块内的代价为该块的最小生成树边权和（因为只需要足够的边使块内连通即可传递能量）。

总代价为各块代价之和。

我们需要最小化总代价。

如果整个点集连通且能量和为 0，那么只需要一棵生成树即可，代价为最小生成树权值和。

但可能分成多个块更优，因为有些边代价很高，不如分开成独立块，但独立块需要满足能量和为 0。

算法步骤

由于 $N \le 16$，可以枚举所有子集。

1. 预处理每个子集 $S$ 的能量和 $sum[S] = \sum_{i \in S} A_i$。
2. 预处理每个子集 $S$ 的最小生成树权值 $mst[S]$（如果 $S$ 连通），如果不连通则设为无穷大。
3. 状态压缩 DP：设 $dp[mask]$ 表示将点集 $mask$ 划分成若干连通块（每个块能量和为 0）的最小总代价。
   • 初始化 $dp[0] = 0$，其他为无穷大。
   • 转移：枚举 $mask$ 的非空子集 $sub$，如果 $sum[sub] = 0$ 且 $mst[sub]$ 有限，则 $dp[mask] = \min(dp[mask], dp[mask \oplus sub] + mst[sub])$。
   • 注意：子集枚举需要优化，可以枚举 $mask$ 的所有子集。
4. 答案：$dp[(1<<N)-1]$，如果无穷大则输出 Impossible。

复杂度

• 子集数量 $2^N \le 65536$。
• 预处理 $mst[S]$：对每个子集 $S$ 求最小生成树，可以用 Kruskal，边数最多 $M \le 120$，对于每个子集 $O(M \log M)$ 可能太慢。但 $N$ 小，我们可以预处理所有边，对于每个子集只考虑端点都在 $S$ 中的边，然后运行 Kruskal。复杂度 $O(2^N \cdot M \log M)$，大约 $65536 \times 120 \times \log 120 \approx 65536 \times 120 \times 7 \approx 5.5 \times 10^7$，可能可接受。
• DP 转移：枚举所有 mask 和子集，复杂度 $O(3^N)$（因为每个 mask 的子集枚举总复杂度 $3^N$），$3^{16} \approx 4.3 \times 10^7$，可接受。

预处理 MST

对于每个子集 $S$，我们只考虑那些两个端点都在 $S$ 中的边，然后运行 Kruskal 算法。如果选出的边数不足以使 $S$ 连通（即边数 < |S|-1 或连通分量 >1），则 $mst[S] = \infty$。

细节

• 注意 $sum[S]$ 可能为 0，但 $S$ 可能不连通，这时 $mst[S]$ 为无穷大，不能用作一个块。
• 如果 $S$ 只有一个点，且 $A_i=0$，那么不需要边，$mst[S]=0$；如果 $A_i \neq 0$，则 $sum[S] \neq 0$，不会用作一个块。
• 最终答案可能为 0（如果初始能量全为 0）。

样例验证

对于样例： $A=[50,-20,-30]$ 边： 0-1:10 1-2:20 0-2:100

子集：

• {0}: sum=50 ≠0
• {1}: sum=-20 ≠0
• {2}: sum=-30 ≠0
• {0,1}: sum=30 ≠0
• {0,2}: sum=20 ≠0
• {1,2}: sum=-50 ≠0
• {0,1,2}: sum=0，MST 边为 0-1(10) 和 1-2(20)，权值和 30。

所以 $dp[111] = 30$。

输出 30。

总结

本题是状态压缩 DP 结合最小生成树的应用。关键是将问题转化为划分连通块，每个块内能量和为 0，且块内用最小生成树传递能量。预处理每个子集的最小生成树权值，然后 DP 求解最小总代价。