输入

9
1 2 1
2 4 3
2 5 4
1 3 2
3 6 5
3 7 1
7 9 4
7 8 0
9

输出

31

叉掉了第二篇树状数组的题解，死于没有处理 $0$。