海底高铁

题目背景

大东亚海底隧道连接着厦门、新北、博艾、那霸、鹿儿岛等城市,横穿东海,耗资1000亿博艾元,历时15年,于公元2058年建成。凭借该隧道,从厦门可以乘坐火车直达台湾、博艾和日本,全程只需要4个小时。

题目描述

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

输入输出格式

输入格式


第一行两个整数,N,M。 接下来一行,M个数字,表示Pi 接下来N-1行,表示第i段铁路的Ai,Bi,Ci

输出格式


一个整数,表示最少花费

输入输出样例

输入样例 #1

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

输出样例 #1

6394

说明

2到3以及8到9买票,其余买卡。 对于30%数据 M=2 对于另外30%数据 N<=1000 ,M<=1000 对于100%的数据 M,N<=100000,Ai,Bi,Ci<=100000