你的房间里有一棵圣诞树。圣诞树是一个拥有 $n$ 个顶点和 $n - 1$ 条边的连通无向图。树上的每个顶点都有一个灯泡。顶点 $v$ 处的灯泡亮度为 $a_v$ 单位。

这棵树很漂亮，而且发出的光非常强烈。然而，你感到有些疲倦并想睡个午觉。如果能把灯光调暗一点就好了，但并没有这样的选项。相反，你可以给边定向，以使树的照明度降低。对于每条边 $(u, v)$，选择恰好一个方向（$u \to v$ 或 $u \leftarrow v$），光线可以沿着该方向传播。对于顶点 $v$，定义其对比度（contrast）为所有满足“存在一条从 $u$ 到 $v$ 的有向路径”的顶点 $u$ 的 $a_u$ 之和。

在所有可能的给树边定向的方法中，所有顶点的对比度之和的最小可能值是多少？

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 250$)，表示测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 500$)，表示树中顶点的数量。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$)，表示各个顶点中灯泡的亮度。

接下来的 $n - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i \neq v_i \le n$)，表示节点 $u_i$ 和 $v_i$ 之间的一条无向边。这些边构成一棵树。

所有测试用例中 $n$ 的总和不超过 500。

输出格式

对于每个测试用例，输出一行，包含一个整数：最小可能的对比度之和。

样例

输入样例 1

2
2
10 20
1 2
4
10 30 60 100
1 2
2 3
2 4

输出样例 1

40
290

说明

在第一个测试用例中，你应该将边定向为 $1 \to 2$。此时顶点 1 的对比度为 10（它仅被自身照亮，且 $a_1 = 10$），顶点 2 的对比度为 30（它被顶点 1 和 2 照亮，且 $a_1 + a_2 = 30$）。

在第二个测试用例中，你可以将边定向为 $1 \to 2$、$2 \to 3$ 和 $2 \to 4$。