test 1 failed.
Input:
5
1 2 3
2 3 1
3 1 3
4 2 3
5 3 5
Expected:
12 8 10 17 25
Got:
20 13 13 22 28