长途奔袭

小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。

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