XYZ 公司已在沿太平洋东海岸位于不同地区的几个岛屿发现了 5 种稀有的矿藏。该公司认为，这将是一个获利最好的机会。然而，由于金融危机，该公司并没有足够的人手和金钱在所有岛屿上建立矿田。因此，公司委员会选择了一些有较高的矿石储量岛屿，并派出一名调查员对这些岛屿制作了岛上的矿石分布调查。调查结果显示，每个岛上有许多连接在一起的村庄。由于耗费时间，调查员并没有记录的地图中的所有路径。只是记下了一条到达每个村庄的路径，从一个村庄到达另一个，有一个且只有一条路径（地图绘制像一棵树）。 该公司计划在每个岛屿的其中一个村庄建立分工厂。所有在岛上不同地方挖来的 5 种稀有矿产将被发送到这个分工厂，后成为一个复合金属。因此途径的道路必须被重修过，才能通过数量庞大的车队。为了尽量减少对道路交通的建设成本，公司决定扩大原有的路径，而不是兴建新的道路。此外，该公司决定兴建村庄的矿田，以确保他们的工人可以进入采矿。（如果子工厂坐落在一个村庄中，矿田也可以建在该村庄。） 由于这些岛屿的矿石储量非常高，每一种罕见的矿物只需要一矿田开采即可。鉴于目前所选择的岛屿的地图，你需要找到在每个岛上的建立子工厂的最优村庄，并从该村庄开始扩展道路，以采集所有 5 种稀有的矿产。

第一行，包含一个整数 $T$ $(1 \le T \le 50)$，表示岛屿的数目。 每组测试数据，第一行一个整数 $N$ $(5 \le N \le 1000)$，表示岛上村庄的个数。 接下来一行 $N$ 个数 $m_1, m_2, \dots, m_N$ $(0 \le m_i \le 5)$，表示第 $i$ 个村庄所拥有的稀有矿藏的种类，$0$ 表示该村庄没有稀有矿藏（每一个村庄至多只有一种矿藏）。 接下来 $N-1$ 行，描述了这个岛上连接 $N$ 个村庄的地图。每行三个数 $x, y, d$ $(1 \le x, y \le N, 1 \le d \le 10000)$，表示从 $x$ 和 $y$ 两个村庄之间有一条距离为 $d$ 的路。

每行输出一个整数。在每个岛上所需的最少扩建道路的长度。