
ZOJ Problem Set  3527
2300 years ago, Moriya Suwako was defeated by Yasaka Kanako in the Great Suwa War. As the goddess of mountains in Gensokyo, she was planning to make a comeback and regain faith among humans.
To achieve her great plan, she decides to build shrines in human villages. Of course, each village can bulid at most one shrine. If she builds a shrine in the ith village, she can get F_{i} faith points. Because of geological differences and the Quantum Entanglement theory, each village has one and only one "entangled" village P_{i} (it is a kind of oneway relationship). If Suwako builds shrines both in the ith village and the P_{i}th village, the faith she get from the ith village will changes by G_{i} points (it can result to a negative value of faith points). If she only builds a shrine in the P_{i}th village, but not in the ith village, the faith she get will not changes. Now, please help Suwako to find out the maximal faith points she can get. InputThere are multiple test cases. For each test case: The first line contains an integer N (2 <= N <= 100000) indicates the number of villages in Gensokyo. Then followed by N lines, each line contains three integers F_{i} (0 <= F_{i} <= 100000) G_{i} (100000 <= G_{i} <= 100000) P_{i} (1 <= P_{i} <= N and P_{i} will not point to the ith village itself). OutputFor each test case, output the maximal faith points that Suwako can get. Sample Input2 3 1 2 2 2 1 4 3 2 2 4 3 3 2 1 1 5 2 2 Sample Output3 9 Author: JIANG, Kai 