塔瓦斯住在塔瓦斯波利斯。塔瓦斯波利斯有 n 个城市,编号从 1 到 n,由 n - 1 条双向道路连接。任意两个城市之间都存在一条路径。每条路也都有长度。
Tavas 最喜欢的字符串是二进制字符串(它们只包含 0 和 1)。对于任何二进制字符串,如 s = s1s2...sk,T(s) 就是它的优点。 T(s) 可以计算如下:
考虑该字符串中正好有 m 个 1 块(s 中的 1 块是 s 中仅包含 1 的最大连续子串),长度为 x1, x2, ..., xm。
定义 $$T(s) = \sum_{i=1}^{m} f_{x_i}$$ 其中 f 是给定序列(如果 m = 0,则 T(s) = 0)。
Tavas 喜欢查询。他要求你回答 q 个问题。在每个查询中,他都会给你数字 v、u、l,你应该打印以下数字:
考虑从城市 v 到城市 u 的道路:e1,e2,...,例如。
构建长度为 x 的二进制字符串 b,使得:bi = 1 当且仅当 l ≤ w(ei) 其中 w(e) 是道路 e 的长度。
您应该为此查询打印 T(b)。
输入
输入的第一行包含整数 n 和 q(2 ≤ n ≤ 105 且 1 ≤ q ≤ 105)。
下一行包含 n - 1 个空格分隔的整数 f1, f2, ..., fn - 1 (|fi| ≤ 1000)。
接下来的 n - 1 行包含道路的详细信息。每行包含整数 v、u 和 w,这意味着城市 v 和 u 之间有一条长度为 w 的道路(1 ≤ v,u ≤ n 且 1 ≤ w ≤ 109)。
接下来的 q 行包含查询的详细信息。每行包含整数 v、u、l(1 ≤ v、u ≤ n、v ≠ u 且 1 ≤ l ≤ 109)。
输出
在一行中打印每个查询的答案。
示例
输入 #1
2 3 10 1 2 3 1 2 2 1 2 3 1 2 4
输出 #1
10 10 0
输入 #2
6 6 -5 0 0 2 10 1 2 1 2 3 2 3 4 5 4 5 1 5 6 5 1 6 1 1 6 2 1 6 5 3 6 5 4 6 4 1 4 2
输出 #2
10 -5 -10 -10 -5 0