ALO is a world of magic and elves. The magic can be upgraded and make more power. The elf Leafa occasionally gets a book that records the most powerful magic matrix. Now the wind elves have decided to conjure up the magic matrix, bombing out the most beautiful fireworks to celebrate their spirit festival.
The magic matrix is a combination of magic, which has a strict hierarchy (like a tree). The wind elves can produce the lowest level of magic directly. Low level magic can be upgraded to a higher magic by consuming one specified hand scroll, which will create magic power in the air and become a higher level of magic.
The upgraded magic can still be upgraded to a higher level of magic until it reaches the highest level of magic. Once the magic reach the highest level, the magic matrix will absorb all the magic power in the air. Note magic upgradation is a continuous process, which means you must perform a series of upgradation at a time, in order to make a lowest level of magic into the highest. If you don’t continuously upgraded to the highest level, the magic you made and the magic power the process produced in the air will disappear immediately.
Now the wind elves took all the magic hands scroll out and began to read the magic books that Leafa had found. As the wisest wind elves, the Lord wants you to help build the magic matrix with the most magic power.
The first line includes a integer number n(n ≤ 100000), types of magic (not including the highest magic, and the highest magic is magic 0)
Then there are n line. Each line includes three numbers, and in the i-th line:
The first integer is prei(0 ≤ prei ≤ n) , that the magic i can be upgraded to the magic prei.
The second integer is numi(numi ≤ 40000), which means wind elves have numi hand scroll to perform such upgradation.
The third integer is poweri(poweri ≤ 1000), which means one such upgradation will produce poweri magic power in the air.
One number, the most magic power.