Задано дерево з \(N\) вершин та \(N-1\) різних кольорів. Кожен колір має свою вартість \(Ci\).

Необхідно пофарбувати кожне ребро в свій колір таким чином, щоб будь-які два інцедентні ребра (ребра які мають спільну вершину) були пофарбовані в різні кольори, і сума вартостей використаних кольорів була мінімальна.

Формат вхідних даних

Перший рядок містить кількість тестів \(T\) (\(1 \le T \le 16\))

Перший рядок кожного тесту містить ціле число \(N\) (\(1 \le N \le 100\)).
Другий рядок містить \(N-1\) ціле число \(Ci\) - вартість кожного кольору (\(1 \le Ci \le 1000\)).
Кожен з наступних \(N-1\) рядків містить по два числа \(V1 V2\) - чергове ребро дерева.

Формат вихідних даних

Для кожного тесту виведіть в окремому рядку - вартість найдешевшого пофарбування дерева.

Приклад вхідних даних

2
5
1 2 3 4
1 2
2 3
2 4
4 5
6
16 4 1 8 2
1 3
3 5
6 3
3 2
4 3

Приклад вихідних даних

7
31