Топскій бажає побудувати мережу з доставки інформації. Мережа містить вихідний сервер та кілька дзеркальних серверів як показано на малюнку. Вхідні дані знаходяться в початковому сервері (в корені на малюнку 1), в той час як їх копії доставляються до деяких дзеркальних серверів (вершини 2 та 5 на малюнку 1). Коли вузол посилає запит на пошук даних, то він намагається знайти їх місце розташування наступним чином. \begin{enumerate} \item Перевіряємо, чи знаходиться копія даних у вузлі. Якщо так, то запит виконаний. Інакше переходимо на крок 2. \item Передаємо запит батьку, який здійснює крок \textbf{1}. \end{enumerate} \includegraphics{https://static.e-olymp.com/content/74/74dc1d0e865c9bc90e76b6fa575090a3ee7fcb83.jpg} Вартість виконання запиту \textbf{C}(\textbf{v}) визначається як сума ваг ребер на шляху. Якщо \textbf{C}(\textbf{v}) не більша за верхню межу \textbf{Q}(\textbf{v}), то вартість пошуку вважається прийнятною. Топскій передбачає також існування невід'ємної вартості \textbf{S}(\textbf{v}) запису даних у вершині \textbf{v}. Вихідний сервер спеціальний, вартість збереження даних в ньому дорівнює \textbf{0}. Топскій бажає розташувати на серверах копії даних таким чином, щоб вартість пошуку для всіх вершин була прийнятною, а сумарна вартість запису даних була б найменшою. \InputFile Перший рядок містить кількість тестів \textbf{t} (\textbf{t} ≤ \textbf{20}). Кожний тест починається цілим числом \textbf{n} (\textbf{1 }≤ \textbf{n} ≤ \textbf{1000}), яке вказує на кількість серверів. Далі йдуть \textbf{n} рядків, кожний з яких містить чотири цілих числа \textbf{F_v} (\textbf{0} ≤ \textbf{F_v} ≤ \textbf{n}), \textbf{Q_v}, \textbf{S_v} и \textbf{W_v} (\textbf{0} ≤ \textbf{Q_v}, \textbf{S_v}, \textbf{W_v} ≤ \textbf{10^5}). В рядку \textbf{i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}), \textbf{F_v} означає батька вершини \textbf{i} (якщо \textbf{F_v} дорівнює \textbf{0}, то \textbf{i} є вихідним сервером, \textbf{Q_v} дорівнює \textbf{-1}, \textbf{S_v} дорівнює \textbf{0} і \textbf{W_v} дорівнює \textbf{0}), \textbf{Q_v} є верхньою границею вартості пошуку, \textbf{S_v} дорівнює вартості запису даних у вершині \textbf{i}, а \textbf{W_v} дорівнює вазі ребра, що сполучає вершини \textbf{i} та \textbf{F_v}. \OutputFile Для кожного тесту в окремому рядку вивести мінімальну вартість затрат на зберігання даних.