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