问题 O: 四叶草魔杖
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
陶醉在彩虹光芒笼罩的美景之中，探险队员们不知不觉已经穿过了七色虹，到达了目的 地，面前出现了一座城堡和小溪田园，城堡前的木牌上写着“Poetic Island”。
“这一定就是另外两位护法的所在地了……我们快进去吧！”
探险队员们快步进入了城堡，城堡大厅的羊毛沙发上坐着两个人。
“你们是 Nescafe 的护法吧？”
“是的哦~ 我们就是圣剑护法 rainbow 和魔杖护法 freda~ 你们来这里做什么呢~”
“我们是来拜访圣主和四位护法的……”
“可是圣主 applepi 已经前往超自然之界的学校（Preternatural Kingdom University，简 称 PKU）修炼魔法了，要想见到他，必须开启 Nescafe 之塔与超自然之界的通道。但是圣主 规定，开启通道的方法不能告诉任何外人。我只能提示你们，开启通道的钥匙就与四位护法 有关 T_T”
探险队员环视四周，突然，其中一人的目光停留在了魔杖之上。“hoho~ 魔杖！传说中 开启异时空通道的钥匙不就叫四叶草魔杖吗？四叶草有力量、信心、希望和幸运四片叶子， 护法恰好有神刀、飞箭、圣剑、魔杖四位！aha~我找到答案了！”
“好吧，那我们就满足你们的愿望~”
魔杖护法 Freda 融合了四件武器，于是魔杖顶端缓缓地生出了一棵四叶草，四片叶子幻 发着淡淡的七色光。圣剑护法 rainbow 取出了一个圆盘，圆盘上镶嵌着 N 颗宝石，编号为 0∼N−1。第 i 颗宝石的能量是 Ai。如果 Ai>0，表示这颗宝石能量过高，需要把 Ai 的能量传 给其它宝石；如果 Ai<0，表示这颗宝石的能量过低，需要从其它宝石处获取−Ai 的能量。保 证∑Ai=0。只有当所有宝石的能量均相同时，把四叶草魔杖插入圆盘中央，才能开启超自 然之界的通道。
不过，只有 M 对宝石之间可以互相传递能量，其中第 i 对宝石之间无论传递多少能量， 都要花费 Ti 的代价。探险队员们想知道，最少需要花费多少代价才能使所有宝石的能量都 相同？
不过，只有 M 对宝石之间可以互相传递能量，其中第 i 对宝石之间无论传递多少能量， 都要花费 Ti 的代价。探险队员们想知道，最少需要花费多少代价才能使所有宝石的能量都 相同？
输入
第一行两个整数 N、M。 第二行 N 个整数AiA_iAi。
接下来 M 行每行三个整数 pi,qi,Ti，表示在编号为pi和 qi的宝石之间传递能量需要花 费 Ti 的代价。
数据保证每对 pi、qi 最多出现一次。
接下来 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% 的数据，2≤N≤8
对于 100% 的数据，2≤N≤16，0≤M≤N×(N−1)/2，0≤pi,qi<N，−1000≤Ai≤1000
0≤Ti≤1000，∑Ai=0。
对于 100% 的数据，2≤N≤16，0≤M≤N×(N−1)/2，0≤pi,qi<N，−1000≤Ai≤1000
0≤Ti≤1000，∑Ai=0。