No testdata at current.

Background

土拨鼠要去拜访他的亲戚并回家看电视 但他走的很慢 他又想以最快的速度到达亲戚家并回到家看电视

Description

现在有$m$条路通往亲戚家(亲戚家有$n$个,土拨鼠要到达第$n$个亲戚家,可能无法直接到达,但可以间接到达并在到达的亲戚家里做客)同时他的路程是$w$,注意我们给出的路都是可以双向通行的

Format

Input

第一行一个正整数n，m 接下来一行$n$个数 $a_1, a_2, a_3 ...... a_n$，$a_i$表示土拨鼠要在第$i$个亲戚家要停留的时间 下面$m$行 每行三个整数$u, v, w$表示第$u$个亲戚家到第$v$个亲戚家的路程$w$

Output

一个整数 输出土拨鼠到达第$n$个亲戚家并回家的最短路程

Samples

Limitation

$1\leq n\leq 10000$

$2\leq m\leq 2000$

$1 \leq u,v \leq n$

$1 \leq w \leq 100000000$