Background

A国有N个城市，编号为1...N。小明是编号为1的城市中一家公司的员工，今天突然接到了上级通知需要去编号为N的城市出差。

Description

由于疫情原因，很多直达的交通方式暂时关闭，小明无法乘坐飞机直接从城市1到达城市N，需要通过其他城市进行陆路交通中转。小明通过交通信息网，查询到了M条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。

同样由于疫情原因，小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络，小明也查询到了各个城市的隔离信息。(由于小明之前在城市1，因此可以直接离开城市1，不需要隔离)

由于上级要求，小明希望能够尽快赶到城市N，因此他求助于你，希望你能帮他规划一条路线，能够在最短时间内到达城市N。

Format

Input

第1行:两个正整数N,M，N表示A国的城市数量，M表示未关闭的路线数量

第2行:N个正整数，第i个整数C表示到达编号为i的城市后需要隔离的时间

第3...M＋2行:每行3个正整数，u,v,c，表示有一条城市u到城市v的

Output

第1行:1个正整数，表示小明从城市1出发到达城市Ⅳ的最短时间（到达城市N，不需要计算城市N的隔离时间)

Samples

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

13

Limitation

对于100%的数据，1≤N ≤ 1000 , 1 ≤ M ≤10000,1 ≤Ci ≤200,1 ≤ u,v≤N,1 ≤c ≤1000