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

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

Наместнику в деревне v отдаются в подчинение все деревни, на простом пути из которых до столицы находится деревня v. В том числе, наместнику отдается в подчинение деревня v.

Для каждой деревни известна величина ai - количество кораблей, которые эта деревня построит за год, если она не находится в подчинении ни у какого наместника.

Если в деревне v находится наместник, то он действует следующим образом:

• Он выбирает подмножество W деревень, соседних с v, находящихся в его подчинении. В этих деревнях он разворачивает большие мастерские по производству кораблей. Для каждой деревни известно, что если в ней построить мастерскую, то в эту деревню нужно поставлять лес из bi других деревень, и эта мастерская произведет ci кораблей за год.
• Теперь он должен выбрать среди оставшихся деревень в его подчинении ровно Σ bu (u ∈ W) деревень, которые будут заниматься поставкой леса в мастерские. В какую конкретную мастерскую будет поставлять лес каждая из них—не так важно.
• Деревня i, в которой построена мастерская, за год построит ci кораблей.
• Деревня, которая занимается поставками леса, не будет строить корабли.
• Все остальные деревни, в его подчинении, за год построят столько же кораблей, как если бы не находились в его подчинении. То есть, i-я деревня построит ai кораблей за год.

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

Входные данные

В первой строке дано одно целое число t (1 ≤ t ≤ 5000) - количество тестов. Далее следует t тестов.

Каждый тест начинается с одного целого числа n (1 ≤ n ≤ 5000) - количество деревень в Мидгарде.

В следующих n строках дано по три целых числа ai, bi и ci (1 ≤ ai, ci ≤ 109, 1 ≤ bi ≤ n) - количество кораблей, которое деревня построит за год, не находясь в подчинении у наместника, количество деревень, которые должны поставлять лес в эту деревню, если в ней построить мастерскую и количество кораблей, которое деревня построит за год, если в ней построить мастерскую.

В следующих n - 1 строках даны описания дорог в Мидгарде. Каждая строка содержит два целых числа vi, ui - номера деревень, соединенных дорогой. Гарантируется, что сеть дорог образует дерево.

Гарантируется, что сумма n во всех тестах не превышает 5000.

Выходные данные

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