2
9 9
0 3 200
1 3 300
2 3 50
3 4 200
3 5 200
3 6 150
5 6 180
6 7 1000
7 8 500
3 0 1 2
8

4 2
0 1 100
2 1 100
2 0 2
3