2
1000000000 3
1 1 3
1 4 5
3 3 4
10000000 3
1 1 1
3 2 2
1 1000 10000000