Колега з пекла
Кожної ночі сторож повинен перевірити деяку кількість кімнат на заводі у відповідності з графіком, який визначає порядок їх відвідування і час перевірки кожної кімнати. Кожної ночі сторож починає свою роботу з першої кімнати, і йде з заводу додому, коли перевірить останню. За звичай він перевіряє усі кімнати, але у нашій історії він може насправді цього не робити.
Маючи доступ до графіку обходу, його колега хоче повеселитись одну нічь, роздразнивши сторожа і заставивши того піти додому дуже пізно. Для цього він може виконати деякі трюки у деяких кімнатах до того моменту, як прийде сторож і почне свою роботу. Кожен трюк в одній кімнаті вводить сторожа в оману, ніби щось може відбутись у іншій кімнаті. Досконалий трюк заставляє сторожа знаходитись інший проміжок часу у цій кімнаті і продовжити перевірку в іншій кімнаті, яка можливо не співпадає з тією, яку він повинен перевіряти у звичайному режимі. Коли сторож заходить у нову кімнату, він продовжує перевіряти її до кінця (і таким чином може не відвідати усі кімнати). Наприклад, якщо є п'ять кімнат і вони у нормальному режимі інспектуються послідовно, а єдиний трюк здійснюється у кімнаті 2, і змушує сторожа направитись на перевірку кімнати 4, то в результаті сторож здійснить шлях 1 - 2 - 4 - 5 і піде додому. Трюк виявляється ефективним у кімнаті лише коли сторож заходить у неї перший раз, і є неефективним коли сторож відвідує цю кімнату потім. Маючи вказану інформацію, Вам потрібно написати програму, яка допоможе колезі скласти план трюків, які максимізують час перебування сторожа на заводі.
Вхідні дані
Перший рядок містить кількість тестів t. Перший рядок кожного тесту містить кількість кімнат n (0 ≤ n ≤ 100). Наступні n рядків описують кімнати у порядку обходу. Кожен рядок опису містить три цілих числа d td tc, де d - час, який сторож знаходиться у кімнаті у випадку звичайної перевірки, td - час знаходження у кімнаті, у випадку якщо у ній здійснюється трюк, і tc - номер наступної кімнати, куди слід йти у випадку завершення трюку. Початкова кімната завжди має номер 1, а кінцева - номер n.
Вихідні дані
Вивести t рядків, кожен з яких містить відповідь на один тест. Для кожного тесту вивести найбільший час, через який сторож зможе выйти з останньої проінспектованої кімнати.