#1453. 树的难题

树的难题

Description

给出一个无根树。树有N个点,边有权值。每个点都有颜色,是黑色、白色、灰色这三种颜色之一,称为一棵三色

树。可爱的Alice觉得,一个三色树为均衡的,当且仅当,树中不含有黑色结点或者含有至多一个白色节点。然而

,给出的三色树可能并不满足这个性质。所以,Alice打算删去若干条边使得形成的森林中每棵树都是均衡的,花

费的代价等于删去的边的权值之和。请你计算需要花费的代价最小是多少。注意,输入文件包含多组测试数据。

Format

Input

第一行包含一个正整数T,表示有T组测试数据。

接下来依次是T组测试数据。

每组测试数据的第一行包含一个正整数N。

第二行包含N个0、1、2之一的整数,依次表示点1到点N的颜色。

其中,0表示黑色,1表示白色,2表示灰色。

接下来N-1行,每行为三个整数ui、vi、ci,表示一条权值等于ci的边(ui,vi)。

1≤N≤300000,1≤T≤5,0≤ci<=10^9

Output

输出 T行,每行一个整数,依次表示每组测试数据的答案。

Samples

1
5
0 1 1 1 0
1 2 5
1 3 3
5 2 5
2 4 16
10

Limitation

花费 10的代价删去边(1, 2)和边(2, 5)