3
6 4
100 4 3 2 1 100
1 2 1
2 3 2
2 6 100
4 6 1
2 0
1000000000 0
1 0
1000000000
