ACM Revenge

Treasure hunters from all over the world have gathered in front of the Amazing Corridors of Mesopotamia. Everyone in the trade calls the ruin ACM.

Over the years many hunters walked into ACM and never came back. The newly elected leader keeps saying that the time has come to end that history and take revenge. The speech does not move you. You already know what project ACM Revenge is really after, and it is the treasure sleeping inside ACM.

Old Mesopotamian scripts give this much:

1. ACM is a collection of rooms joined by one-way corridors. Nobody can walk a corridor backwards.
2. One room is the entrance and it opens to the outside world. Every room in ACM is reached from the entrance by exactly one path.
3. A room with no outgoing corridor is packed with treasure. The moment somebody reaches such a room, that person and everything inside are teleported out of ACM, landing somewhere near the entrance.
4. Every other room has exactly two outgoing corridors, and a huge stone blocks one of them at any moment. When somebody steps into the free corridor, the stone slides over to block that corridor and frees the other one. Such a room also holds a few traps. One trap kills one person and then stops working, so the same trap never kills twice.

The hunters go in one at a time. A person who steps into a room that still has a working trap dies there, and that trap stops working. A person who steps into a room whose traps are all spent leaves through the free corridor, and the stone changes place at that moment. The scream of a dying hunter carries to the entrance, and the next hunter goes in.

You know the map, the number of traps left in every room, and which corridor is free right now. You want to be the first person to reach a treasure room. The $m$-th hunter to enter ACM is the one who reaches it first, and you need a program to compute $m$.

The input holds several test cases. The first line of each test case gives the number of rooms $N$ in ACM ($1 \le N \le 20000$). The next $N$ lines describe room $1$ through room $N$ in order. The $i$-th of those lines holds three integers $p_i$, $f_i$ and $t_i$ ($0 \le p_i \le N$, $0 \le f_i \le 1$, $0 \le t_i \le 100000$).

$p_i$ is the number of the room at the other end of the corridor leading into room $i$, and $p_i = 0$ means room $i$ is the entrance. $f_i$ is $1$ when that corridor is free right now and $0$ when the stone blocks it. $t_i$ is the number of working traps left in room $i$.

The entrance room always has $f_i = 1$, and every room with no outgoing corridor has $t_i = 0$. A room has either no outgoing corridor or exactly two of them. The last line of the input holds a single $0$.

For each test case print $m - 1$ on one line. That value is the number of people who die before the first hunter reaches a treasure room.