NKOJ 2439 四叶草魔杖（最小生成树、状压动态规划与网络流）

2439 四叶草魔杖

问题描述

魔杖护法Freda结合了四件武器，在其顶端缓缓绽放出一片四叶草状物。四个叶片上漂浮着七彩光芒，在暗处投射出奇幻的光影效果。圣剑护法rainbow从宝库中取出一个圆形盘子，在其表面均匀分布着N个宝石标记点（编号为0到N-1）。每个标记点上的宝石具有一个能量值Ai：若该值大于零，则表示该宝石的能量过高；若小于零，则表示能量不足；总能量之和∑Ai = 0是维持平衡的关键条件。只有当所有宝石的能量达到一致时，并且完成特定的空间排列组合后（即完成特定的空间排列组合后），魔杖顶端才会释放出超自然之界的开启信号——这需要将圆盘中央与魔杖顶端连接起来并施放解除魔法阵卡文特禁制符

输入格式

    第一行两个整数N、M。
    第二行N个整数Ai。
    接下来M行每行三个整数pi,qi,Ti，表示在编号为pi和qi的宝石之间传递能量需要花费Ti的代价。数据保证每对pi、qi最多出现一次。

输出格式

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

样例输入

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

样例输出

30

提示

    对于 50