#873. 海底高铁

海底高铁

题目描述

该铁路经过 NN 个城市,每个城市都有一个站。不过,由于各个城市之间不能协调好,于是乘车每经过两个相邻的城市之间(方向不限),必须单独购买这一小段的车票。第 ii 段铁路连接了城市 ii 和城市 $i+1(1\leq i

输入格式

第一行两个整数,N,MN,M。

接下来一行,MM 个数字,表示 PiP_i。

接下来 N−1N-1 行,表示第 ii 段铁路的 Ai,Bi,CiA_i,B_i,C_i。

输出格式

一个整数,表示最少花费。

样例

9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10
6394

题目来源:洛谷 P3406