[河南省队2012]长途奔袭

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 YZ.in 输出文件 YZ.out

小k所属的联盟PIBC马上要与粉红鱼雷开战了。就在大家准备急行军到战场埋伏粉红鱼雷的时候,小k所属联盟下某TT驾驶员手滑,单独跃迁到了一个不知名的星域并且误入虫洞。

时间不等人,舰队指挥要求这名TT驾驶员立刻返回战场。然而,这名驾驶员所在星域距离战场十分遥远,他位于虫洞入口,需要路过N颗行星。这N颗行星之间有M条双向航道。TT驾驶员为了在最短的时间内赶回战场并侦查附近星域,在航道上,对与这N颗行星,每颗恰好只路过一次。在航道上TT驾驶员有两种前行的方式。一种叫做跃迁,可以瞬间到达下一个地点,但是需要花一定的时间调整转向。另外一种当然就是慢慢爬过去了。但是,由于TT的质量及惯性修正值极大,因此TT在慢慢爬的时候只能向引力更大的行星行驶。但是这名TT驾驶员很笨,不知道该如何规划路线,因此他找到了宇宙中最聪明你帮他规划路线,使他用最少的时间到达战场。

Input

第一行是两个正整数 N, M。 第二行 N 个数 A1~AN,其中Ai表示使用跃迁到达行星 i 所需的转向时间。接下来 M行,每行 3个正整数ui, vi, wi,表示在编号为 ui和vi的行星之间存在一条需要航行wi时间的星际航路。输入数据已经按引力值排序,也就是编号小的行星引力值一定小,且不会有两颗行星引力值相同。

Output

仅包含一个正整数,表示到达战场所需的最少时间。

样例:

YZ.in

3 3

100 1 100

2 1 10

1 3 1

2 3 1

YZ.out

102


对于 30%的数据 N≤20,M≤50;

对于 70%的数据 N≤200,M≤4000;

对于100%的数据N≤800, M≤15000。

输入数据中的任何数都不会超过10^6。

输入数据保证任意两颗行星之间至多存在一条航道,且不会存在某颗行星到自己的航道。