Prospecting

Prospectin' Pete has a lead on a new titanium mine and needs your help pitching a mining operation to investors. The mine can be represented as a tree. The mine entrance is the root, the other nodes are pockets of underground titanium ore, and the edges are potential tunnels Pete can dig between two pockets (or between the mine entrance and one pocket, for edges adjacent to the root). The tunnel connecting the $i$-th ore pocket to its parent has a length of $y_i$ feet. One of the tree leaves contains the motherlode, and each other ore pocket contains $x_i$ dollars worth of ore.

Pete begins at the mine entrance, and his goal is to reach the motherlode. He cannot travel to pocket $i$ until all $y_i$ feet of dirt in the tunnel leading to it has been removed. Once a tunnel has been completely excavated, however, Pete can travel it in both directions as many times as he wants.

Pete explores the mine by repeating the following steps in order:

1. Pete chooses a tunnel that he can reach from his current location and that has not yet been fully excavated.
2. Pete digs through one foot of the chosen tunnel. This costs him one dollar.
3. If the tunnel is now completely clear, Pete travels through it to the newly opened pocket and mines the ore. If that pocket contains the motherlode, he stops exploring. Otherwise, he sells the ore in that pocket for $x_i$ dollars and continues.

The tunnel Pete digs in step 1 does not need to be adjacent to his current location, as long as he can reach it by traveling through completely excavated tunnels. He may also choose a different tunnel each round, even if the tunnel he dug in the previous round is still not fully excavated. If Pete ends a round with no money and without having reached the motherlode, the operation is a bust and Pete goes home bankrupt.

Pete knows the layout of the mine and the amount of ore in each pocket, but he has not yet decided how to dig. In addition to the riches he earns from the mine, he needs some startup money to reach the motherlode, so he is courting investors. He wants to give them two numbers:

• The minimum number of dollars $a$ that Pete must start with so that the venture succeeds in the worst case, meaning he is guaranteed to reach the motherlode no matter which tunnel he chooses to dig in each round.
• The minimum number of dollars $b$ that Pete must start with to reach the motherlode in the best case, where Pete chooses tunnels optimally.

With these numbers, investors can decide how much to fund Pete based on how much they trust him to dig optimally without mistakes.

Given the mine layout, compute $a$ and $b$.

Figure F.1: Illustrations of sample inputs 1 (left) and 2. Edges represent tunnels and nodes represent ore pockets. Ore values $x_i$ in each pocket and tunnel lengths $y_i$ are written in black text. ML stands for the motherlode. Node indices are in red.

The first line contains an integer $n$ ($2 \le n \le 200000$), the number of nodes in the tree. The next $n-1$ lines each contain three integers $p_i$, $x_i$, and $y_i$ for the $i$-th node. $p_i$ ($0 \le p_i < i$) is the index of the parent of node $i$. Parent index 0 means the parent is the mine entrance. $x_i$ is the ore value in node $i$, and $y_i$ ($1 \le y_i \le 1000$) is the length of the tunnel connecting node $p_i$ to node $i$. Exactly one node has $x_i = -1$, which marks the motherlode. All other values satisfy $0 \le x_i \le 1000$.

Node 0 is the mine entrance. It holds no ore and has no input line. You may assume the motherlode is a leaf, so no node has it as a parent.

Print two space-separated integers $a$ and $b$, the worst-case and best-case investment Pete needs to clear a path to the motherlode, as described above.

Consider the mine in the first sample input, shown on the left of Figure F.1. Pete needs 8 dollars to guarantee that he reaches the motherlode even with poor digging choices. In the worst case, he spends 2 dollars to completely clear the tunnel into pocket 2, then 5 more dollars to clear the tunnel to pocket 4. With his last dollar, he either digs his way to the motherlode or opens the tunnel to pocket 1, which gives him enough money to reach the motherlode in the next round of digging. In the best case, he needs only one dollar. He spends it to dig through the tunnel into pocket 1, and with the 3 dollars of ore he mines there, he digs through the two tunnels on the path from the entrance to the motherlode.

The second sample input, shown on the right of Figure F.1, works the same way. In one worst case, Pete excavates three feet of the tunnel into pocket 1, two feet of the tunnel into pocket 3, and one foot of the tunnel into pocket 4, none of it yielding ore. This costs 6 dollars. With a seventh dollar, he is guaranteed to tunnel into an ore pocket that finances exploration of the rest of the mine, including the motherlode. In the best case, he needs only one dollar. He digs to pocket 2, then 4, then 3, then 1, finding the motherlode.