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