Edward and Bella

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

     Bella被邪恶的吸血鬼家族抓到了Volterra,别以此要挟Edward为他们效力。Edward决定去魔鬼般的Volterra城将Bella解救出来,他得到了Elise的帮助。Elise通过可以预见未来的能力为Edward描绘出一副Volterra城的地图。
     Elise还知道,Volterra城绝不是那么简单,城里面有n个传送阵,Edward只有控制所有的传送阵才能逃出Volterra城。在地图上找出了这n个传送阵的位置,并且知道一些传送阵跑到另外传送阵的所消耗的时间,她要求Edward走最短的时间控制所有的以免节外生枝。
     Edward发现他可以在已经控制了的传送阵之间任意传送而不许要消耗时间,但是还没有控制的传送阵之间还不能进行传送。他想知道怎样才能够在最短的时间内控制所有的传送阵。

Input

 输入n和m,分别表示图中的节点数和边数(n<100, n-1 <= m < 1000)。Edward初始时在节点1位置。
后面跟着1行,有n个元素,表示控制每个节点所需要的时间。
接下来m行,每行包含a,b,c,三个数,表示a、b之间传送所消耗的时间为c。
(多组数据,处理到文件结尾。保证题目数据合法)

Output

输出最短时间,如果无解输出”-1”。

Sample Input

3 3
1 10 6
1 2 1
1 3 2
2 3 3

Sample Output

20

Hint

 

Source

fenggang