9 6
2 3 1000
3 4 10
4 5 1000
6 7 1000
7 8 10
8 9 1000
6
2 6 10
5 9 10
1 3 100
1 4 100
1 7 50
1 8 50