TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2439
  • 問題
  • P2439四叶草魔杖
    制限 : 時間制限 : 10000 MS   メモリ制限 : 165536 KB
    問題説明

    (clover.cpp/.in/.out) 
      魔杖护法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。