Given is a tree with N weighted vertices and N-1 weighted edges. The i-th vertex has a weight of A_{i}. The i-th edge has a weight of W_{i} and connects vertices u_{i} and v_{i}.

Let \operatorname{dist}(x,y) be the sum of weights of the edges in the unique [simple path] connecting vertices x and y.

Let \operatorname{V}(x,y) be the set of vertices appearing in the unique simple path connecting vertices x and y (including x and y).

You are asked Q queries. In the i-th query, you are given two integers x_{i} and y_{i} and you need to compute:

\sum\limits_{k\in \operatorname{V}(x_{i},y_{i})}(\operatorname{dist}(x_{i},k)-\operatorname{dist}(k,y_{i}))\cdot A_{k}

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line contains two integers N and Q.
- The second line contains N integers A_{1},A_{2},\dots,A_{N}.
- Each of the next N-1 lines contains three integers u_{i}, v_{i} and W_{i}.
- Each of the next Q lines contains two integers x_{i} and y_{i}.

------ Output Format ------ 

For each query, print the answer to it on a new line.

------ Constraints ------ 

$1≤T≤10^{3}$
$2 ≤N ≤2\cdot10^{5}$
$1 ≤Q ≤2\cdot10^{5}$
$1 ≤A_{i},W_{i} ≤10^{4}$
$1≤u_{i},v_{i},x_{i},y_{i}≤N$
$x_{i}\ne y_{i}$
$u_{i}\ne v_{i}$
- The sum of $N$ across all test cases does not exceed $2\cdot 10^{5}$.
- The sum of $Q$ across all test cases does not exceed $2\cdot 10^{5}$.

------ subtasks ------ 

Subtask #1 (20 points): $u_{i}=i,v_{i}=i+1$
Subtask #2 (80 points): Original constraints

----- Sample Input 1 ------ 
2
5 2
5 3 3 1 2
1 2 2
2 3 1
2 4 1
1 5 2
4 5
5 4
10 5
3 6 9 2 3 8 3 7 9 7
1 2 4
1 3 6
1 4 8
4 5 9
1 6 2
5 7 3
3 8 7
3 9 2
7 10 9
9 2
2 1
8 5
3 2
3 10
----- Sample Output 1 ------ 
1
-1
-96
-12
-252
-24
-69
----- explanation 1 ------ 
Test Case $1$: 
- For the first query, $\operatorname{V}(4,5)=\{4,2,1,5\}$. The answer is $1\cdot(0-5)+3\cdot(1-4)+5\cdot(3-2)+2\cdot(5-0)=1$
- For the second query, $\operatorname{V}(5,4)=\{5,1,2,4\}$. The answer is $2\cdot(0-5)+5\cdot(2-3)+3\cdot(4-1)+1\cdot(5-0)=-1$

Difficulty: VERY_HARD

Starter code:

Solutions:
from collections import defaultdict
import math
import sys
sys.setrecursionlimit(int(200000.0))

def get_mid(s, e):
	return s + (e - s) // 2

def build_tree(arr):
	n = len(arr)
	n1 = 2 ** math.ceil(math.log2(n))
	st = [0] * (2 * n1 - 1)

	def builder(segment_start, segment_end, st_idx):
		if segment_end == segment_start:
			st[st_idx] = segment_start
		else:
			mid = get_mid(segment_start, segment_end)
			b1 = builder(segment_start, mid, st_idx * 2 + 1)
			b2 = builder(mid + 1, segment_end, st_idx * 2 + 2)
			if arr[b1] <= arr[b2]:
				st[st_idx] = b1
			else:
				st[st_idx] = b2
		return st[st_idx]
	builder(0, n - 1, 0)
	return st

def query_tree(st, arr, query_start, query_end):
	len_arr = len(arr)

	def q(range_start, range_end, st_idx):
		if query_start <= range_start and range_end <= query_end:
			return st[st_idx]
		elif query_end < range_start or range_end < query_start:
			return -1
		else:
			mid = get_mid(range_start, range_end)
			b1 = q(range_start, mid, st_idx * 2 + 1)
			b2 = q(mid + 1, range_end, st_idx * 2 + 2)
			assert b1 > -1 or b2 > -1
			if b2 == -1:
				return b1
			elif b1 == -1:
				return b2
			elif arr[b1] <= arr[b2]:
				return b1
			else:
				return b2
	return q(0, len_arr - 1, 0)

class F:

	def __init__(self, node, parent, level, d, c, s):
		self.node = node
		self.parent = parent
		self.level = level
		self.d = d
		self.c = c
		self.s = s
		self.state = 0

def do_dfs2(adj, root, A):
	N = max(adj)
	trail = []
	levels_by_node = [0] * (N + 1)
	D = [0] * (N + 1)
	C = [0] * (N + 1)
	S = [0] * (N + 1)
	stack = [F(root, -1, 0, d=0, c=0, s=A[root])]
	while stack:
		f = stack[-1]
		if f.state == 1:
			if f.parent >= 0:
				trail.append(f.parent)
			stack.pop()
			continue
		trail.append(f.node)
		levels_by_node[f.node] = f.level
		D[f.node] = f.d
		C[f.node] = f.c
		S[f.node] = f.s
		for (child, weight) in adj[f.node]:
			if child != f.parent:
				stack.append(F(child, f.node, f.level + 1, d=f.d + weight, c=f.c + (f.d + weight) * A[child], s=f.s + A[child]))
		f.state = 1
	return (trail, [levels_by_node[t] for t in trail], D, C, S)

def do_dfs(adj, root, A):
	N = max(adj)
	trail = []
	levels_by_node = [0] * (N + 1)
	D = [0] * (N + 1)
	C = [0] * (N + 1)
	S = [0] * (N + 1)

	def dfs(node, parent, level, d, c, s):
		trail.append(node)
		levels_by_node[node] = level
		D[node] = d
		C[node] = c
		S[node] = s
		for (child, weight) in adj[node]:
			if child != parent:
				dfs(child, node, level + 1, d=d + weight, c=c + (d + weight) * A[child], s=s + A[child])
				trail.append(node)
	dfs(root, -1, 0, d=0, c=0, s=A[root])
	return (trail, [levels_by_node[t] for t in trail], D, C, S)

def solve(A, edges, queries):
	adj = defaultdict(list, {})
	for (e1, e2, w) in edges:
		adj[e1].append((e2, w))
		adj[e2].append((e1, w))
	root = next((k for (k, c) in adj.items() if len(c) == 1))
	(trail, levels, D, C, S) = do_dfs2(adj, root, A)
	node_to_idx = {}
	for (idx, node) in enumerate(trail):
		if node not in node_to_idx:
			node_to_idx[node] = idx
	st = build_tree(levels)

	def lca(x, y):
		xi = node_to_idx[x]
		yi = node_to_idx[y]
		levels_idx = query_tree(st, levels, min(xi, yi), max(xi, yi))
		return trail[levels_idx]

	def a(x, y):
		p = lca(x, y)
		sum_a_p1 = S[x] - S[p] + A[p]
		sum_a_p2 = S[y] - S[p]
		coef1 = D[x] - D[y] + 2 * D[p]
		coef2 = D[x] - D[y] - 2 * D[p]
		sum_of_akdk_p1 = C[x] - C[p] + A[p] * D[p]
		sum_of_akdk_p2 = C[y] - C[p]
		return coef1 * sum_a_p1 + coef2 * sum_a_p2 - 2 * sum_of_akdk_p1 + 2 * sum_of_akdk_p2
	return [a(x, y) for (x, y) in queries]

def pp(input):
	cases = int(input())
	for case in range(cases):
		(N, Q) = map(int, input().split())
		A = [0] + list(map(int, input().split()))
		edges = [tuple(map(int, input().split())) for _ in range(N - 1)]
		queries = [tuple(map(int, input().split())) for _ in range(Q)]
		ans = solve(A, edges, queries)
		for a in ans:
			print(a)
if 'paalto' in sys.argv[0] or sys.argv[0].endswith('pydevconsole.py'):
	lines = iter(x.split('\n'))
else:
	lines = iter(sys.stdin.read().split('\n'))
pp(lambda : next(lines))


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 6)

def dfs(p, prev, sx, sy, ss, lvl):
	level[p] = lvl
	parent[p][0] = prev
	for i in range(1, 20):
		if parent[p][i - 1] != -1:
			parent[p][i] = parent[parent[p][i - 1]][i - 1]
	px[p] = sx + a[p - 1]
	py[p] = sy
	ps[p] = ss
	for x in range(len(child[p])):
		(i, w) = child[p][x]
		if i == prev:
			continue
		dfs(i, p, sx + a[p - 1], sy + w, ss + w * (sx + a[p - 1]), lvl + 1)

def lca(u, v):
	if level[u] > level[v]:
		(u, v) = (v, u)
	dist = level[v] - level[u]
	for i in range(19, -1, -1):
		if dist >> i & 1:
			v = parent[v][i]
	if u == v:
		return u
	for i in range(19, -1, -1):
		if parent[u][i] != parent[v][i]:
			u = parent[u][i]
			v = parent[v][i]
	return parent[u][0]

def solve(x, y):
	Lca = lca(x, y)
	sxx = px[x] - px[Lca] + a[Lca - 1]
	syx = py[x] - py[Lca]
	ssx = ps[x] - ps[Lca] - px[Lca] * syx
	sxy = px[y] - px[Lca] + a[Lca - 1]
	syy = py[y] - py[Lca]
	ssy = ps[y] - ps[Lca] - px[Lca] * syy
	sumx = ssx + syx * sxy + (sxy - a[Lca - 1]) * syy - ssy
	sumy = ssy + syy * sxx + (sxx - a[Lca - 1]) * syx - ssx
	ans = sumx - sumy
	return ans

def answer():
	for i in range(q):
		(x, y) = map(int, input().split())
		print(solve(x, y))
for T in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		child[u].append([v, w])
		child[v].append([u, w])
	(px, py, ps) = ([0] * (n + 1), [0] * (n + 1), [0] * (n + 1))
	level = [0] * (n + 1)
	parent = [[-1 for i in range(20)] for j in range(n + 1)]
	dfs(1, -1, 0, 0, 0, 0)
	answer()


import sys
input = sys.stdin.readline
T = int(input())

def testcase():

	def process(u, v, w, crate_list=False):
		isolated = False
		if tree_back[u - 1] != None:
			known = u - 1
			unknown = v - 1
		elif tree_back[v - 1] != None:
			known = v - 1
			unknown = u - 1
		else:
			isolated = True
		if isolated:
			if crate_list:
				u_unsolved.append(u)
				v_unsolved.append(v)
				w_unsolved.append(w)
			return False
		else:
			cache_sum[unknown] = cache_sum[known] + w
			cache_mul[unknown] = cache_mul[known] + 2 * cache_sum[unknown] * A[unknown]
			tree_back[unknown] = known
			hier[unknown] = hier[known] + 1
			if child_cnt[known] == 0:
				cache_branch[unknown] = cache_branch[known]
				branch_hier[unknown] = branch_hier[known]
				child_cnt[known] += 1
			else:
				connect_node.append(known)
				branch_id[0] = branch_id[0] + 1
				cache_branch[unknown] = branch_id[0]
				branch_hier[unknown] = branch_hier[known] + 1
				child_cnt[known] += 1
			cache_weight_sum[unknown] = cache_weight_sum[known] + A[unknown]
			return True

	def process_only(unknown, known, w):
		cache_sum[unknown] = cache_sum[known] + w
		cache_mul[unknown] = cache_mul[known] + 2 * cache_sum[unknown] * A[unknown]
		tree_back[unknown] = known
		hier[unknown] = hier[known] + 1
		if child_cnt[known] == 0:
			cache_branch[unknown] = cache_branch[known]
			branch_hier[unknown] = branch_hier[known]
			child_cnt[known] += 1
		else:
			connect_node.append(known)
			branch_id[0] = branch_id[0] + 1
			cache_branch[unknown] = branch_id[0]
			branch_hier[unknown] = branch_hier[known] + 1
			child_cnt[known] += 1
		cache_weight_sum[unknown] = cache_weight_sum[known] + A[unknown]

	def calc(x, c, yd):
		if c == 0:
			return -cache_mul[x] + (cache_sum[x] - yd) * cache_weight_sum[x]
		else:
			return -(cache_mul[x] - cache_mul[tree_back[c]]) + (cache_sum[x] + cache_sum[c] - yd) * (cache_weight_sum[x] - cache_weight_sum[tree_back[c]])
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	(u_unsolved, v_unsolved, w_unsolved) = ([], [], [])
	(cache_sum, cache_mul, cache_weight_sum, tree_back, hier) = ([0] * N, [0] * N, [0] * N, [None] * N, [None] * N)
	branch_hier = [None] * N
	branch_parent = [-1]
	connect_node = [-1]
	branch_id = [0]
	(cache_branch, child_cnt) = ([None] * N, [0] * N)
	cache_weight_sum[0] = A[0]
	(tree_back[0], hier[0], branch_hier[0]) = (-1, 0, 0)
	raw_con = [[] for _ in range(N)]
	raw_con_len = [[] for _ in range(N)]
	for i in range(N - 1):
		(u, v, w) = map(int, input().split())
		process(u, v, w, crate_list=False)
		raw_con[u - 1].append(v - 1)
		raw_con_len[u - 1].append(w)
		raw_con[v - 1].append(u - 1)
		raw_con_len[v - 1].append(w)
	to_be_visited = raw_con[0]
	visit_len = raw_con_len[0]
	last_node = [0] * len(to_be_visited)
	while to_be_visited:
		unknown = to_be_visited.pop()
		known = last_node.pop()
		dist = visit_len.pop()
		if tree_back[unknown] == None:
			process_only(unknown, known, dist)
		for (i, child) in enumerate(raw_con[unknown]):
			if child != known:
				to_be_visited.append(child)
				last_node.append(unknown)
				visit_len.append(raw_con_len[unknown][i])
	for i in range(Q):
		(x, y) = map(int, input().split())
		x = x - 1
		y = y - 1
		(treeX, treeY) = (x, y)
		while cache_branch[treeX] != cache_branch[treeY]:
			if branch_hier[treeX] == branch_hier[treeY]:
				if cache_branch[treeX] != 0:
					treeX = connect_node[cache_branch[treeX]]
				if cache_branch[treeY] != 0:
					treeY = connect_node[cache_branch[treeY]]
			elif branch_hier[treeX] > branch_hier[treeY]:
				treeX = connect_node[cache_branch[treeX]]
			else:
				treeY = connect_node[cache_branch[treeY]]
		if hier[treeX] > hier[treeY]:
			common_node = treeY
		else:
			common_node = treeX
		if common_node == x:
			ans = -calc(y, common_node, 0)
		elif common_node == y:
			ans = calc(x, common_node, 0)
		else:
			xd = cache_sum[x] - cache_sum[common_node]
			yd = cache_sum[y] - cache_sum[common_node]
			ans = calc(x, common_node, yd) - calc(y, common_node, xd) - (xd - yd) * A[common_node]
		print(ans)
for _ in range(T):
	testcase()