背景

陶醉在彩虹光芒笼罩的美景之中,探险队员们不知不觉已经穿过了七色虹,到达了目的地,面前出现了一座城堡和小溪田园,城堡前的木牌上写着“Poetic Island”。
“这一定就是另外两位护法的所在地了……我们快进去吧!”
探险队员们快步进入了城堡,城堡大厅的羊毛沙发上坐着两个人。
“你们是Nescafé 的护法吧?”
“是的哦~ 我们就是圣剑护法rainbow 和魔杖护法freda~ 你们来这里做什么呢~”
“我们是来拜访圣主和四位护法的……”
“可是圣主applepi 已经前往超自然之界的学校(Preternatural Kingdom University,简称PKU)修炼魔法了,要想见到他,必须开启Nescafé 之塔与超自然之界的通道。但是圣主规定,开启通道的方法不能告诉任何外人。我只能提示你们,开启通道的钥匙就与四位护法有关T_T”
探险队员环视四周,突然,其中一人的目光停留在了魔杖之上。“hoho~ 魔杖!传说中开启异时空通道的钥匙不就叫四叶草魔杖吗?四叶草有力量、信心、希望和幸运四片叶子,护法恰好有神刀、飞箭、圣剑、魔杖四位!aha~我找到答案了!”
“好吧,那我们就满足你们的愿望~”

描述

魔杖护法Freda 融合了四件武器,于是魔杖顶端缓缓地生出了一棵四叶草,四片叶子幻发着淡淡的七色光。圣剑护法rainbow 取出了一个圆盘,圆盘上镶嵌着N 颗宝石,编号为0~N-1。第i 颗宝石的能量是Ai。如果Ai>0,表示这颗宝石能量过高,需要把Ai 的能量传给其它宝石;如果Ai<0,表示这颗宝石的能量过低,需要从其它宝石处获取-Ai 的能量。保证ΣAi =0。只有当所有宝石的能量均相同时,把四叶草魔杖插入圆盘中央,才能开启超自然之界的通道。
不过,只有M 对宝石之间可以互相传递能量,其中第i 对宝石之间无论传递多少能量,都要花费Ti 的代价。探险队员们想知道,最少需要花费多少代价才能使所有宝石的能量都相同?

输入格式

第一行两个整数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% 的数据,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。

来源

石家庄二中【Nescafé 29】杯NOIP模拟赛