比赛场次 156
比赛名称 20120720
比赛状态 已结束比赛成绩
开始时间 2012-07-20 08:00:00
结束时间 2012-07-20 12:00:00
开放分组 全部用户
注释介绍 群众喜闻乐见的有关于游戏的题目
题目名称 长途奔袭
输入输出 YZ.in/out
时间限制 1000 ms (1 s)
内存限制 32 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar了反取字名我擦 AAAAAAAAAA 2.001 s 2.05 MiB 100
GravatarMakazeu AAAAAAAAAA 2.135 s 29.83 MiB 100
Gravatar王者自由 AAAAAAATTT 3.350 s 22.29 MiB 70

长途奔袭

★   输入文件:YZ.in   输出文件:YZ.out   简单对比
时间限制:1 s   内存限制:32 MiB

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

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