지옥에서 온 동료

매일 밤 경비원은 공장의 방들을 정해진 순서대로 점검한다. 그는 $1$번 방에서 시작하며, 마지막 방인 $n$번 방을 점검한 뒤 공장을 나와 집으로 돌아간다. 정상적인 점검에서는 $i$번 방에 $d_i$의 시간 동안 머문 다음 $i+1$번 방으로 이동한다.

점검 일정을 알고 있는 짓궂은 동료는 경비원을 최대한 오래 붙잡아 두고 싶어 한다. 경비원이 도착하기 전에, 동료는 원하는 방들의 임의의 부분집합에 장난을 설치할 수 있다. 경비원이 장난이 설치된 방을 점검하면 속아 넘어가, 그 방에 $d_i$ 대신 $td_i$의 시간 동안 머물고, 이후 $i+1$번 방 대신 $tc_i$번 방(어느 방이든 될 수 있다)으로 이동한다.

장난은 경비원이 그 방에 처음 들어갔을 때에만 작동한다. 이후 그 방을 다시 방문할 때에는 정상적으로 행동한다($d_i$만큼 머물고 $i+1$번 방으로 이동). 장난은 경비원을 뒤쪽 방으로 보낼 수도 있어 같은 방을 여러 번 지날 수 있고, 앞쪽 방으로 보낼 수도 있어 일부 방을 아예 건너뛸 수도 있다. 예를 들어 방이 다섯 개이고 순서대로 점검할 때, $2$번 방에만 장난을 설치하고 그것이 $4$번 방을 가리킨다면 경비원은 1 → 2 → 4 → 5 순으로 이동한 뒤 집으로 가며, $3$번 방은 점검하지 않는다.

경비원은 마지막 방인 $n$번 방을 정상적으로 점검했을 때에만 집으로 돌아간다. 동료가 경비원을 공장에 머물게 할 수 있는 최대 총 시간을 구하여라.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 방의 개수를 나타내는 정수 $n$ (0 ≤ $n$ ≤ 100)이 주어진다. 그 다음 $n$개의 줄에 방들이 순서대로 주어지며, $i$번째 줄에는 세 정수 $d_i$, $td_i$, $tc_i$ (1 ≤ $tc_i$ ≤ $n$)가 주어진다. 각각 $i$번 방의 정상 점검 시간, $i$번 방에 장난이 설치되었을 때의 점검 시간, 그리고 $i$번 방에 장난이 설치되었을 때 경비원이 이동하는 방의 번호이다. $1$번 방이 항상 첫 방이고 $n$번 방이 항상 마지막 방이다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 경비원이 마지막 방을 정상적으로 점검하고 나가기 전까지 공장에 붙잡혀 있을 수 있는 최대 총 시간이다.