10
1 2 2
2 3 -1
1 4 4
2 5 2
3 6 -2
4 5 -5
5 6 -3
4 7 4
5 8 10
7 8 -8
1 8
4 6
2 8
7 3
-1