4 6
2 1 4
2 2 4
3 2 4 5
1 5
2 20 1 100
1 18 1 200
3 28 1 800
21 30 3 1500
1 30 2 100
19 21 1 400