ACM 복수전

세계 각지에서 모인 보물 사냥꾼이 메소포타미아의 놀라운 회랑 앞에 모였다. 사냥꾼들 사이에서는 이 유적을 ACM이라고 부른다.

지난 세월 동안 수많은 사냥꾼이 ACM에 들어갔다가 돌아오지 못했다. 새로 뽑힌 우두머리는 이제 그 역사를 끝내고 복수할 때가 왔다고 목소리를 높인다. 그 연설에 마음이 움직이지는 않는다. ACM 복수전이 실제로 무엇을 노리는지 이미 알기 때문이다. 목적은 ACM 안에 잠든 보물이다.

오래된 메소포타미아 문서에서 알아낸 사실은 다음과 같다.

ACM은 일방통행 회랑으로 이어진 방의 모음이다. 회랑을 거슬러 올라갈 수는 없다.
바깥 세상과 이어진 입구 방이 하나 있다. ACM의 모든 방에는 입구에서 출발하는 경로가 정확히 하나씩 있다.
나가는 회랑이 없는 방에는 보물이 가득하다. 누군가 이런 방에 닿는 순간 그 사람과 방 안의 보물이 함께 ACM 바깥, 입구 근처로 순간이동한다.
나머지 방에는 나가는 회랑이 정확히 두 개 있고, 그중 한쪽은 항상 거대한 돌이 막고 있다. 누군가 열린 회랑으로 들어서면 돌이 그 회랑을 막고 반대쪽 회랑을 연다. 이런 방에는 함정도 몇 개씩 놓여 있다. 함정 하나는 사람 한 명을 죽인 뒤 그대로 작동을 멈추므로, 같은 함정이 두 번 죽이지는 않는다.

사냥꾼은 한 번에 한 명씩 들어간다. 아직 살아 있는 함정이 남은 방에 들어선 사람은 그 자리에서 함정 하나에 걸려 죽고, 그 함정은 작동을 멈춘다. 함정이 모두 소진된 방에 들어선 사람은 열린 회랑으로 빠져나가며, 그 순간 돌이 자리를 바꾼다. 죽는 사냥꾼의 비명은 입구까지 들리고, 그러면 다음 사냥꾼이 들어간다.

지도와 각 방에 남은 함정 수, 지금 열려 있는 회랑을 모두 알고 있다. 보물 방에 가장 먼저 닿는 사람이 되고 싶다. ACM에 들어가는 $m$ 번째 사냥꾼이 처음으로 보물 방에 닿는다. $m$ 을 계산하는 프로그램이 필요하다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 ACM의 방 개수 $N$ 이 주어진다 ( $1 \le N \le 20000$ ). 이어지는 $N$ 개의 줄은 $1$ 번 방부터 $N$ 번 방까지를 순서대로 설명한다. $i$ 번째 줄에는 세 정수 $p_i$ , $f_i$ , $t_i$ 가 주어진다 ( $0 \le p_i \le N$ , $0 \le f_i \le 1$ , $0 \le t_i \le 100000$ ).

$p_i$ 는 $i$ 번 방으로 들어오는 회랑의 반대쪽 끝에 있는 방 번호이고, $p_i = 0$ 이면 $i$ 번 방이 입구다. $f_i$ 는 그 회랑이 지금 열려 있으면 $1$ , 돌에 막혀 있으면 $0$ 이다. $t_i$ 는 $i$ 번 방에 남아 있는 함정 수다.

입구 방은 항상 $f_i = 1$ 이고, 나가는 회랑이 없는 방은 모두 $t_i = 0$ 이다. 한 방에서 나가는 회랑은 아예 없거나 정확히 두 개다. 입력의 마지막 줄에는 $0$ 하나만 주어진다.

문제

입력

출력