crazyzhk 居住的城市结构是一棵树。某一天，城市的网络需要升级。为了实现这一目标，需要部署路由器。每个路由器覆盖它所在的节点及其相邻节点。在每个节点放置路由器都有一个关联的代价 $a_i$。问题是：如何以最小的代价部署路由器，以确保每个节点都被覆盖？

输入格式

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

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示给定树中的顶点数量。

每个测试用例的第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le 10^5$)，表示在每个节点设置路由器的代价。

接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示树中顶点 $u$ 和 $v$ 之间有一条边。

数据保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示确保每个节点都被覆盖的最小代价。

样例

输入 1

2
7
13 20 1 20 6 9 8
1 2
1 3
2 4
2 5
3 6
5 7
4
1 17 13 4
1 2
1 3
3 4

输出 1

27
5