Input

5

1 2 3

1 3 2

2 4 2

2 5 3

2

4 5

Output

7

但是我的这份AC代码输出8

https://www.luogu.com.cn/record/127343062

错的原因是注释掉了check函数对于node数组的排序

(不过可能是我的写法比较奇怪才会在这个样例挂掉，这个hack可能不具有普遍性)