В Мидгарде есть $$$n$$$ деревень, соединенных сетью дорог. В Мидгарде $$$n - 1$$$ дорога, и по этим дорогам можно от любой деревни добраться до любой другой. Иными словами, сеть дорог образует дерево. Деревня номер $$$1$$$ является столицей. Мидгардцы добывают много дерева, из которого затем строят корабли. Сейчас правитель Мидгарда хочет за год построить большой флот и отправиться на завоевание новых земель и ресурсов. Для этого, он решил применить следующую стратегию:
Правитель может разослать любое количество наместников. При условии, что наместники действуют оптимально, определите, какое максимальное количество кораблей может быть суммарно построено всеми деревнями за год.
В первой строке дано одно целое число $$$t$$$ — количество тестов ($$$1 \le t \le 5\,000$$$). Далее следует $$$t$$$ тестов.
Каждый тест начинается с одного целого числа $$$n$$$ — количество деревень в Мидгарде ($$$1 \le n \le 5000$$$).
В следующих $$$n$$$ строках дано по три целых числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ — количество кораблей, которое деревня построит за год, не находясь в подчинении у наместника, количество деревень, которые должны поставлять лес в эту деревню, если в ней построить мастерскую и количество кораблей, которое деревня построит за год, если в ней построить мастерскую ($$$1 \le a_i, c_i \le 10^9$$$; $$$1 \le b_i \le n$$$).
В следующих $$$n - 1$$$ строках даны описания дорог в Мидгарде. Каждая строка содержит два целых числа $$$v_i$$$, $$$u_i$$$ — номера деревень, соединенных дорогой. Гарантируется, что сеть дорог образует дерево.
Гарантируется, что сумма $$$n$$$ во всех тестах не превышает $$$5\,000$$$.
Для каждого теста выведите одно целое число — максимальное количество кораблей, которые все деревни могут суммарно построить за год при правильном распределении наместников.
3
3
1 1 10
1 1 9
5 1 11
1 2
2 3
4
2 4 9
2 2 6
1 4 7
4 4 8
1 2
2 3
1 4
7
3 1 10
2 4 6
3 2 8
2 3 4
1 1 9
2 1 6
1 2 4
1 2
2 3
3 4
2 5
5 6
5 7
14
10
22