Фарбування ребер
Вам дано дерево T з n вершинами. Вершини дерева пронумеровані цілими числами від 1 до n. Розглянемо набір різних кольорів, пронумерованих цілими числами від 1 до n - 1. Кожен колір має свою вартість. Вам надано послідовність вартостей кольорів cost[1], cost[2], ..., cost[n−1]. Ваше завдання — пофарбувати кожне ребро в свій колір так, щоб будь-які два інцидентні ребра були пофарбовані в різні кольори, і сума вартостей кольорів на ребрах була мінімальною.
Вхідні дані
Перша стрічка містить кількість тестів t (1 ≤ t ≤ 16).
Перша стрічка кожного тестового прикладу містить ціле число n (1 ≤ n ≤ 100). Друга стрічка містить n - 1 ціле додатне число cost[1], cost[2], ..., cost[n−1] (1 ≤ cost[color] ≤ 1000). Кожна з наступних n - 1 стрічок містить два числа u і v — чергове ребро дерева T.
Вихідні дані
Для кожного тесту виведіть в окремому рядку одне ціле число — вартість найдешевшого допустимого фарбування ребер дерева.