Топскій бажає побудувати мережу з доставки інформації. Мережа містить вихідний сервер та кілька дзеркальних серверів як показано на малюнку. Вхідні дані знаходяться в початковому сервері (в корені на малюнку 1), в той час як їх копії доставляються до деяких дзеркальних серверів (вершини 2 та 5 на малюнку 1). Коли вузол посилає запит на пошук даних, то він намагається знайти їх місце розташування наступним чином.
Перевіряємо, чи знаходиться копія даних у вузлі. Якщо так, то запит виконаний. Інакше переходимо на крок 2.
Передаємо запит батьку, який здійснює крок 1.
Вартість виконання запиту C(v) визначається як сума ваг ребер на шляху. Якщо C(v) не більша за верхню межу Q(v), то вартість пошуку вважається прийнятною. Топскій передбачає також існування невід'ємної вартості S(v) запису даних у вершині v. Вихідний сервер спеціальний, вартість збереження даних в ньому дорівнює 0. Топскій бажає розташувати на серверах копії даних таким чином, щоб вартість пошуку для всіх вершин була прийнятною, а сумарна вартість запису даних була б найменшою.
Перший рядок містить кількість тестів t (t ≤ 20). Кожний тест починається цілим числом n (1 ≤ n ≤ 1000), яке вказує на кількість серверів. Далі йдуть n рядків, кожний з яких містить чотири цілих числа F_v (0 ≤ F_v ≤ n), Q_v, S_v и W_v (0 ≤ Q_v, S_v, W_v ≤ 10^5). В рядку i (1 ≤ i ≤ n), F_v означає батька вершини i (якщо F_v дорівнює 0, то i є вихідним сервером, Q_v дорівнює -1, S_v дорівнює 0 і W_v дорівнює 0), Q_v є верхньою границею вартості пошуку, S_v дорівнює вартості запису даних у вершині i, а W_v дорівнює вазі ребра, що сполучає вершини i та F_v.
Для кожного тесту в окремому рядку вивести мінімальну вартість затрат на зберігання даних.