Co-workers from Hell

Every night a watchman inspects the chambers of a factory in a fixed order. He starts at chamber $1$ and, after inspecting the final chamber $n$, leaves the factory and goes home. In a normal inspection he stays in chamber $i$ for $d_i$ units of time and then moves on to chamber $i+1$.

A mischievous co-worker who has seen the schedule wants to keep the watchman at work as long as possible. Before the watchman arrives, the co-worker may place a trick in any subset of the chambers. When the watchman inspects a chamber that holds a trick, he is fooled: he stays there $td_i$ units of time instead of $d_i$, and afterwards moves to chamber $tc_i$ (which may be any chamber) instead of chamber $i+1$.

A trick works only the first time the watchman enters that chamber; on every later visit to it he behaves normally (stays $d_i$ and moves to chamber $i+1$). A trick may send him backward, so he can pass through some chambers several times, or forward, so he may skip some chambers entirely. For instance, with five chambers inspected in order, if the only trick is placed in chamber $2$ and points to chamber $4$, the watchman walks 1 → 2 → 4 → 5 and then goes home, never checking chamber $3$.

The watchman goes home only when he performs a normal inspection of the final chamber $n$. Determine the maximum total time the co-worker can force the watchman to stay in the factory.

The first line contains the number of test cases $T$.

Each test case starts with a line containing an integer $n$ (0 ≤ $n$ ≤ 100), the number of chambers. The next $n$ lines describe the chambers in order; the $i$-th line contains three integers $d_i$, $td_i$, and $tc_i$ (1 ≤ $tc_i$ ≤ $n$): the normal inspection time in chamber $i$, the inspection time when chamber $i$ is tricked, and the chamber the watchman moves to when chamber $i$ is tricked. Chamber $1$ is always the first chamber and chamber $n$ is always the final one.

For each test case, print a single line with one integer: the maximum total time the watchman can be forced to remain in the factory before he leaves the final chamber by a normal inspection.