Села лісорубів
У Мідгарді є n сіл, з'єднаних мережею доріг. У Мідгарді n - 1 дорога, і по цих дорогах можна дістатися від будь-якого села до будь-якого іншого. Іншими словами, мережа доріг утворює дерево. Село номер 1 є столицею. Мідгардці добувають багато дерева, з якого потім будують кораблі. Зараз правитель Мідгарда хоче за рік побудувати великий флот і вирушити на завоювання нових земель і ресурсів. Для цього він вирішив застосувати таку стратегію:
Відправити в деякі села намісників. Причому, на простому шляху з села, в яке відправлений намісник, до столиці не повинно знаходитися іншого села, в яке теж відправлений намісник. Зверніть увагу, що можна відправити одного намісника в столицю, але в такому випадку ні в яке інше село намісника вже відправити не можна.
Наміснику в селі v віддаються в підпорядкування всі села, на простому шляху з яких до столиці знаходиться село v. В тому числі, наміснику віддається в підпорядкування село v.
Для кожного села відома величина a[i] - кількість кораблів, які це село побудує за рік, якщо воно не знаходиться в підпорядкуванні у жодного намісника.
Якщо в селі v знаходиться намісник, то він діє наступним чином:
Він обирає підмножину W сіл, сусідніх з v, що знаходяться в його підпорядкуванні. У цих селах він розгортає великі майстерні з виробництва кораблів. Для кожного села відомо, що якщо в ньому побудувати майстерню, то в це село потрібно постачати ліс з
b[i]інших сіл, і ця майстерня виробитьc[i]кораблів за рік.Тепер він повинен обрати серед решти сіл в його підпорядкуванні рівно Σ
b[u](u ∈ W) сіл, які будуть займатися постачанням лісу в майстерні. В яку конкретну майстерню буде постачати ліс кожне з них — не так важливо.Село i, в якому побудована майстерня, за рік побудує
c[i]кораблів.Село, яке займається постачанням лісу, не буде будувати кораблі.
Всі інші села, в його підпорядкуванні, за рік побудують стільки ж кораблів, як якщо б не знаходилися в його підпорядкуванні. Тобто, i-те село побудує
a[i]кораблів за рік.
Правитель може розіслати будь-яку кількість намісників. За умови, що намісники діють оптимально, визначте, яку максимальну кількість кораблів може бути сумарно побудовано всіма селами за рік.
Вхідні дані
У першому рядку дано одне ціле число t (1 ≤ t ≤ 5000) - кількість тестів. Далі слідує t тестів.
Кожен тест починається з одного цілого числа n (1 ≤ n ≤ 5000) - кількість сіл у Мідгарді.
У наступних n рядках дано по три цілі числа a[i], b[i] і c[i] (1 ≤ a[i], c[i] ≤ 10^9, 1 ≤ b[i] ≤ n) - кількість кораблів, яке село побудує за рік, не знаходячись в підпорядкуванні у намісника, кількість сіл, які повинні постачати ліс в це село, якщо в ньому побудувати майстерню і кількість кораблів, яке село побудує за рік, якщо в ньому побудувати майстерню.
У наступних n - 1 рядках дано описи доріг у Мідгарді. Кожен рядок містить два цілі числа v[i], u[i] - номери сіл, з'єднаних дорогою. Гарантується, що мережа доріг утворює дерево.
Гарантується, що сума n у всіх тестах не перевищує 5000.
Вихідні дані
Для кожного тесту виведіть одне ціле число - максимальну кількість кораблів, які всі села можуть сумарно побудувати за рік при правильному розподілі намісників.