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