2
4 4
1 2 100
2 3 100
3 4 100
4 1 200
1
1 4
6 9
2 4 5
5 1 7
3 6 6
3 1 4
2 3 2
1 2 1
6 5 42
4 5 3
4 6 5
4
1 3
3 4
5 4
6 1