#D. 拜访亲戚

    Type: Default 1000ms 256MiB

拜访亲戚

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

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

Format

Input

第一行一个正整数n,m 接下来一行nn个数 a1,a2,a3......ana_1, a_2, a_3 ...... a_naia_i表示土拨鼠要在第ii个亲戚家要停留的时间 下面mm行 每行三个整数u,v,wu, v, w表示第uu个亲戚家到第vv个亲戚家的路程ww

Output

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

Samples



Limitation

1n100001\leq n\leq 10000

2m20002\leq m\leq 2000

1u,vn1 \leq u,v \leq n

1w1000000001 \leq w \leq 100000000

zzy

Not Attended
Status
Done
Rule
Ledo
Problem
4
Start at
2024-5-26 15:45
End at
2024-5-26 16:25
Duration
0.7 hour(s)
Host
Partic.
2