eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Коллега из преисподней

Коллега из преисподней

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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

Имея доступ к графику обхода, его коллега хочет повеселиться одну ночь, раздразнив сторожа и заставив того пойти домой очень поздно. Для этого он может сделать некоторые трюки в некоторых комнатах до того момента, как придет сторож и начнет свою работу. Каждый трюк в одной комнате вводит сторожа в заблуждение, как будто что-то может произойти в другой комнате. Совершенный трюк заставляет сторожа находиться другое количество времени в этой комнате и продолжить проверку в другой комнате, возможно не совпадающей с той, которую он должен проверять в обычном режиме. Когда сторож заходит в новую комнату, он продолжает проверять ее до конца (и таким образом может не посетить все комнаты). Например, если имеются пять комнат и они в нормальном режиме инспектируются последовательно, а единственный трюк совершается в комнате 2, заставляющий сторожа направиться на проверку комнаты 4, то в итоге сторож проделает путь 1 - 2 - 4 - 5 и уйдет домой. Трюк оказывается эффективным в комнате только когда сторож заходит в нее первый раз, и является неэффективным когда сторож посещает эту комнату в будущем. Имея указанную информацию, Вам следует написать программу, которая поможет коллеге составить план трюков, максимизирующий время пребывания сторожа на заводе.

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

Первая строка содержит количество тестов t. Первая строка каждого теста содержит количество комнат n (0n100). Следующие n строк описывают комнаты в порядке обхода. Каждая строка описания содержит три целых числа d td tc, где d - время которое сторож находится в комнате в случае обычной проверки, td - время нахождения в комнате, в случае если в ней совершается трюк, и tc - номер следующей комнаты, куда следует идти в случае совершения трюка. Начальная комната всегда имеет номер 1, а конечная - номер n.

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

Вывести t строк, каждая из которых содержит ответ на один тест. Для каждого теста вывести наибольшее время, через которое сторож сможет выйти из последней проинспектированной комнаты.

Пример

Входные данные #1
1
5
1 2 2
1 2 4
1 1 4
1 2 5
1 2 4
Выходные данные #1
10