3 7
2 0 1
6 2 10
5 4 100
2 1 1 7 7
0 5 6 1000
0 5 1 10000
3 1 5 7 7 0 100000
1 1 1000000
2 5 4 7 5
2 5 1 7 7