No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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$