Migrated from Lutece 3177 机器学习

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

众所周知，故障机器人（鸡煲）是杀戮尖塔中的最强角色。

这一天，鸡煲打算收集敌人图鉴。尖塔一共有 $n$ 层，每一层有一个敌人。尖塔中有 $m$ 条通道，每条通道连接着两个不同的楼层，且通道只能从低层通向高层（楼层高度与编号成正比），通过第 $i$ 条通道所需要的时间为 $t_i$。同时，鸡煲得到了涅奥的帮助，可以在任何地点用 $a_i$ 的时间传送到第 $i$ 层（一开始，鸡煲身处尖塔外，这意味着要先传送才能进入尖塔）。

为了收集每个敌人的图鉴，需要到达敌人对应的楼层。鸡煲一共准备了 $n$ 枚烟雾弹，所以你不用担心鸡煲会暴毙。但是由于烟雾弹数量有限，鸡煲只能到达每个楼层恰好一次才能有把握收集全图鉴。

现在鸡煲向你提出一个问题：他至少需要花费多少时间才能收集所有敌人的图鉴。

Input

第一行两个正整数 $n,m(1\leq n\leq800,1\leq m\leq15000)$。 第二行 $n$ 个整数 $a_1,a_2,...,a_n(0\leq a_i\leq10^6)$，表示传送到第 $i$ 层所需时间。 接下来 $m$ 行，每行三个正整数 $u_i,v_i,t_i(1\leq u,v\leq n,0\leq t_i\leq10^6)$，表示在 $u_i$ 和 $v_i$ 间存在一条需要用时 $t_i$ 的边。

Output

Samples

4 4
4 3 2 5
2 4 2
3 4 3
3 2 2
1 3 3

11

Note

鸡煲先传送到第 $2$ 层，移动到第 $4$ 层，然后传送到第 $1$ 层，再传送到第 $3$ 层，总花费时间为 $11$。

Resources

2024 UESTC ICPC Training for Graph