树是一个具有 $n$ 个节点和 $n - 1$ 条边的连通图。

给定一棵带权树，共有 $n$ 个节点。第 $i$ 个节点的权重为 $wn_i$，代价为 $c_i$。连接节点 $u_i$ 和 $v_i$ 的第 $i$ 条边的权重为 $we_i$。当且仅当一条边满足 $\min(wn_{u_i}, wn_{v_i}) \le we_i \le \max(wn_{u_i}, wn_{v_i})$ 时，称该边为“美丽的”。

你可以进行多次以下操作： * 选择一个节点 $u$，将其权重 $wn_u$ 修改为 $wn'_u$。总代价增加 $c_u |wn_u - wn'_u|$。

求使得所有边都变为“美丽的”所需的最小总代价。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例，输入格式如下：

$n$ $c_1 \ c_2 \ c_3 \ \dots \ c_n$ $wn_1 \ wn_2 \ wn_3 \ \dots \ wn_n$ $u_1 \ v_1 \ we_1$ $u_2 \ v_2 \ we_2$ $\vdots \ \vdots \ \vdots$ $u_{n-1} \ v_{n-1} \ we_{n-1}$

保证： $1 \le T \le 10^3$ $1 \le n \le 10^5$，$\sum n \le 10^6$ * $1 \le c_i, wn_i, we_i \le 10^6$

输出格式

对于每个测试用例，输出一行一个整数，表示最小总代价。

样例

样例输入 1

2
3
2 1 2
9 9 10
1 2 10
1 3 11
3
1 1 2
9 9 10
1 2 10
1 3 11

样例输出 1

3
2