2
4 10
1 1 2
1 2 2
2 1 2
2 2 2
6 5
1 1 4
1 3 1
3 4 5
4 3 2
5 2 1
3 2 10