出差 ### 问题描述 $\mathrm{A}$ 国有 $N$ 个城市, 编号为 $1 \ldots N$ 。小明是编号为 1 的城市中一家公司的员 工, 今天突然接到了上级通知需要去编号为 $N$ 的城市出差。 由于疫情原因, 很多直达的交通方式暂时关闭, 小明无法乘坐飞机直接从 城市 1 到达城市 $N$, 需要通过其他城市进行陆路交通中转。小明通过交通信息 网, 查询到了 $M$ 条城市之间仍然还开通的路线信息以及每一条路线需要花费的 时间。 同样由于疫情原因, 小明到达一个城市后需要隔离观察一段时间才能离开 该城市前往其他城市。通过网络, 小明也查询到了各个城市的隔离信息。(由于 小明之前在城市 1 , 因此可以直接离开城市 1 , 不需要隔离） 由于上级要求, 小明希望能够尽快赶到城市 $\mathrm{N}$, 因此他求助于你, 希望你 能帮他规划一条路线, 能够在最短时间内到达城市 $N$ 。 ### 输入格式 第 1 行: 两个正整数 $N, M, N$ 表示 A 国的城市数量, $M$ 表示末关闭的路 线数量 第 2 行: $N$ 个正整数, 第 $i$ 个整数 $C_{i}$ 表示到达编号为 $\mathrm{i}$ 的城市后需要隔离 的时间 第 $3 \ldots M+2$ 行: 每行 3 个正整数, $u, v, c$, 表示有一条城市 $u$ 到城市 $v$ 的 双向路线仍然开通着, 通过该路线的时间为 $c$ ### 输出格式 第 1 行: 1 个正整数, 表示小明从城市 1 出发到达城市 $N$ 的最短时间（到 达城市 $N$, 不需要计算城市 $N$ 的隔离时间） ### 样例输入 ```text 4 4 5 7 3 4 1 2 4 1 3 5 2 4 3 3 4 5 ``` ### 样例输出 ```text 13 ``` ### 样例说明  ### 评测用例规模与约定 对于 $100 \\%$ 的数据, $1 \leq N \leq 1000,1 \leq M \leq 10000,1 \leq C_{i} \leq 200,1 \leq u, v \leq$ $N, 1 \leq c \leq 1000$