时间限制： 4.0 秒

空间限制： 256 MB

问题描述

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$，分别表示一条旅行路线的起点和终点。

输出格式

输出到标准输出。

输出 $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

样例 1 解释

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

子任务

所有评测用例都满足：$1 \le n, m \le 10^5,~1 \le w_i \le 10^6,~1 \le e \le 10^4$。