题目描述

Z国有N个城市，城市编号从0到N-1，部分城市之间会有公路相连。而某些城市被称作泥泞城市，一旦经过这种城市，在接下来的两段公路上你的移动速度会减慢到初始值的一半。

比如说有4个城市ABCD，公路的连接方式如下所示：
A-B-C-D
且A为泥泞城市。那么从A出发到D的过程中，A-B、B-C这两段路上的移动速度都会减半，而到C-D这段路上又会恢复到原来的速度。

现在告诉你每条道路以及每个城市的情况，求从城市0到城市N-1最少所要花费的时间。
数据保证从城市0到城市N-1必有路。

输入要求

第一行两个整数N、M，分别表示城市数目和道路数目。 (1 <= N,M <= 10^5)
第二行有N个整数a[0]~a[N-1], a[i]=1表示编号为i的城市是泥泞城市，a[i]=0则表示不是。
接下来M行，每行三个整数u,v,w。u,v分别表示这条道路所连接的两个城市的编号，w则表示以初始速度经过这条道路需要多少时间。 (0 <= u,v < N; 1 <= w <= 1000)

输出要求

输出一个整数，表示从城市0到城市N-1最少所要花费的时间。

输入样例

4 4
0 1 0 1
0 1 1
2 0 1000
1 2 1
2 3 1000

输出样例

2000

提示

最短路径： 0->2->3

来源

NBU OJ