1316. 最小花费

C国共有n个城市。有n-1条双向道路,每条道路连接两个城市,任意两个城市之间能互相到达。小R来到C国旅行,他共规划了m条旅行的路线,第i条旅行路线的起点是s i,终点是t i。在旅行过程中,小R每行走一单位长度的路需要吃一单位的食物。C国的食物只能在各个城市中买到,而且不同城市的食物价格可能不同。

然而,小R不希望在旅行中为了购买较低价的粮食而绕远路,因此他总会选择最近的路走。现在,请你计算小R规划的每条旅行路线的最小花费是多少。

输入

第一行包含2个整数n和m。

第二行包含n个整数。第i个整数w i表示城市i的食物价格。

接下来n-1行,每行包括3个整数u, v, e,表示城市u和城市v之间有一条长为e的双向道路。

接下来m行,每行包含2个整数s i和t i,分别表示一条旅行路线的起点和终点。

前10%的评测用例满足:n, m ≤ 20, w i ≤ 20;

前30%的评测用例满足:n, m ≤ 200;

另有40%的评测用例满足:一个城市至多与其它两个城市相连。

所有评测用例都满足:1 ≤ n, m ≤ 10 5,1 ≤ w i ≤ 10 6,1 ≤ e ≤ 10000。

输出

输出m行,分别代表每一条旅行方案的最小花费。

样例

标准输入 复制文本
6 4
1 7 3 2 5 6
1 2 4
1 3 5
2 4 1
3 5 2
3 6 1
2 5
4 6
6 4
5 6 
标准输出 复制文本
35
16
26
13 

提示

对于第一条路线,小R会经过2->1->3->5。其中在城市2处以7的价格购买4单位粮食,到城市1时全部吃完,并用1的价格购买7单位粮食,然后到达终点。

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 0
通过 0