题目描述

小熊的地图上有 $n$ 个景点，每个景点有分数 $s_i$。

$n-1$ 个点对之间有双向直达的公交线路，每条线路有收费 $w_i$。

现在小熊在 $a$ 景点，总司令在 $b$ 景点，他们要在 $a\to b$ 路径上的 $p$ 景点汇合，然后一起去 $q$ 景点。（$q$ 为任意点，每个人不会游览两次 $p$ 景点）

$m$ 次询问，给定 $a,b$，求 $p,q$，使得小熊和总司令花费之和最小的前提下他们经过的景点分数之和最大，输出他们经过的景点分数之和。（指小熊经过的景点分数之和 $+$ 总司令经过的景点分数之和）

重复经过的线路收费重复计算，重复经过的景点分数重复计算。

输入格式

第一行两个整数 $n,m$。分别表示景点个数和询问次数。

接下来一行 $n$ 个整数 第 $i$ 个整数 $s_i$ 表示第 $i$ 个景点的权值。

接下来 $n-1$ 行，每行 $3$ 个整数 $u,v,w$，表示 $u$ 节点和 $v$ 节点之间有一条收费 $w$ 的双向公交路线。

接下来 $m$ 行，每行两个整数 $a$ 和 $b$，表示小熊和总司令所在的景点位置。

输出格式

对于每组询问，每行输出一个整数表示结果。

7 1
1 1 1 1 1 1 1
1 2 3
3 6 -4
2 5 2
1 3 6
2 4 1
3 7 5
4 7

8

10 10
786755 -687509 368192 154769 647117 -713535 337677 913223 -389809 -824004 
1 2 -785875
1 3 -77082
1 4 -973070
3 5 -97388
2 6 -112274
3 7 657757
4 8 741733
3 9 5656
4 10 -35190
3 3
3 10
7 3
5 1
2 10
10 10
1 6
7 2
8 9
9 1

971424
-1257332
1309101
3420605
-2313033
-2567048
-2467802
352646
759321
1368370

提示

样例说明

对于第一组样例，小熊的地图如图所示：

其中 $a=4,b=7$，令 $p=3,q=6$。

小熊的路径为 $4\to2\to1\to3\to6$，花费之和为 $1+3+6+(-4)=6$，景点分数之和为 $1+1+1+1+1=5$。

总司令的路径为 $7\to3\to6$，花费之和为 $5+(-4)=1$，景点分数之和为 $1+1+1=3$。

小熊和总司令花费之和为 $6+1=7$，经过的景点分数之和为 $5+3=8$。

可以证明此时小熊和总司令花费之和最小的前提下他们经过的景点分数之和最大。

---

数据范围

本题采用捆绑测试。

Subtask	$n,m$	$s_i,w_i$	特殊性质	分数
$1$	$=3\times10^5$	$\in\lbrack0,10^6\rbrack$	无	$10$
$2$		$\in\lbrack-10^6,10^6\rbrack$	小熊的地图是一条链
$3$	$=3\times10^2$		无	$5$
$4$	$=3\times10^3$			$15$
$5$	$\le 3\times10^5$			$60$

对于 $100\%$ 的数据，$1\le n,m\le 3\times 10^5$，$\vert s_i\vert,\vert w_i\vert\le10^6$，小熊的地图是一棵树。

（小熊都可以游览景点了，公交价格和景点分数怎么不可以是负数呢？）