5516: 暑期营第七天 旅行

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

志坚者,不以山海为远
户外攀登的有形之山,尚且存在有形之路,而学术科研的无形之山,则需要在无人区独自披荆斩棘,高中三年风雨兼程,MJ早已循滔乎此,望本期理性,加以努力,前进而勿顾后,背黑暗而向光明,为世界进文明为人类造幸福。
学术之巅不止一座,通往成功之路不止一条,如今意志坚定的MJ望着漫漫长路,打算竹杖芒鞋越重山,MJ已知有N个学术发展节点,不同发展节点中有M单向条发展道路,每到达第i个发展节点,MJ就要花费a[i]额外时间去掌握该技能,他终将到达学术之巅(一定可以到达并且学习完N号节点的知识)。

Input

第一行两个整数n,m,分别表示发展节点的个数和发展道路的数量。
第二行共n个数a[i],表示在第i个发展节点掌握技能所花费的时间。
从第三行开始,到第m+2行,每行3个数u,v,d,表示单向发展道路的起点、终点和u到v所需时间。

Output

一行一个整数,表示你从节点1出发,学习完第N个知识所花费的最小时间。

Sample Input Copy

3 2
0 0 0
1 2 1
2 3 1

Sample Output Copy

2