Деревни лесорубов

В Мидгарде есть $n$ деревень, соединенных сетью дорог. В Мидгарде $n - 1$ дорога, и по этим дорогам можно от любой деревни добраться до любой другой. Иными словами, сеть дорог образует дерево. Деревня номер $1$ является столицей. Мидгардцы добывают много дерева, из которого затем строят корабли. Сейчас правитель Мидгарда хочет за год построить большой флот и отправиться на завоевание новых земель и ресурсов. Для этого, он решил применить следующую стратегию:

Отправить в некоторые деревни наместников. Причем, на простом пути из деревни, в которую отправлен наместник, до столицы не должно находиться другой деревни, в которую тоже отправлен наместник. Обратите внимание, что можно отправить одного наместника в столицу, но в таком случае ни в какую другую деревню наместника уже отправить нельзя.
Наместнику в деревне $v$ отдаются в подчинение все деревни, на простом пути из которых до столицы находится деревня $v$ . В том числе, наместнику отдается в подчинение деревня $v$ .
Для каждой деревни известна величина $a\_i$ --- количество кораблей, которые эта деревня построит за год, если она не находится в подчинении ни у какого наместника.
Если в деревне $v$ находится наместник, то он действует следующим образом:
- Он выбирает подмножество $W$ деревень, соседних с $v$ , находящихся в его подчинении. В этих деревнях он разворачивает большие мастерские по производству кораблей. Для каждой деревни известно, что если в ней построить мастерскую, то в эту деревню нужно поставлять лес из $b\_i$ других деревень, и эта мастерская произведет $c\_i$ кораблей за год.
- Теперь он должен выбрать среди оставшихся деревень в его подчинении ровно $\sum\limits\_{u \in W} b\_u$ деревень, которые будут заниматься поставкой леса в мастерские. В какую конкретную мастерскую будет поставлять лес каждая из них --- не так важно.
- Деревня $i$ , в которой построена мастерская, за год построит $c\_i$ кораблей.
- Деревня, которая занимается поставками леса, не будет строить корабли.
- Все остальные деревни, в его подчинении, за год построят столько же кораблей, как если бы не находились в его подчинении. То есть, $i$ -я деревня построит $a\_i$ кораблей за год.

Правитель может разослать любое количество наместников. При условии, что наместники действуют оптимально, определите, какое максимальное количество кораблей может быть суммарно построено всеми деревнями за год.

В первой строке дано одно целое число $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$ .

Деревни лесорубов

문제

입력

출력