3
5 3
0 1 10
0 2 20
0 3 30
4
1 2 3 4
30
5 3
0 1 10
0 2 20
0 3 30
4
1 2 3 4
60
5 3
0 1 10
0 2 20
0 3 30
4
1 2 3 4
10000