Problem J
Trail Mix Grading

Tim and his friends gather to create the best trail mix for their upcoming hike. Each of them brings one unique ingredient, which will be counted as one mixture.

Then, each person chooses whose mixture they want to combine their mixture with. If the chosen mixture is already combined with another mixture, they will also join that mixture.

Finally, to grade these combined mixtures, each person gives a score for a single pair of ingredients. Any mixture featuring that pair will gain that score.

Input

The first line of input contains the number of friends participating (including Tim) $n$ ($2 \leq n \leq 10^5$).

The next $n$ lines each contain a single integer $p_i$ the mixture that the $i$th mixture wants to be combined with ($0 \leq p_i < n$).

Then, for the next $n$ lines, each line contains three numbers $s_i$, $a_i$, $b_i$ ($1 \leq s_i \leq 10^3$, $0 \leq a_i, b_i < n$) the score and two ingredients that the $i$th person gave a score to. $a_i$ and $b_i$ can be equal in case they only want to grade a single ingredient.

Note that $p_i$, $a_i$, and $b_i$ use the order of friends declaring their $p_i$, which starts counting from $0$.

Output

Print the score of the highest graded mixture. If none of the graded pairs are featured in any mixture, print $0$.

5
0
0
1
3
3
5 0 1
5 1 2
5 2 3
5 3 4
5 1 3

10

4
0
2
3
3
4 0 0
1 1 2
1 2 3
1 0 1

4

2
0
1
10 0 1
20 1 0

0