5 3
2 7 1
3 1 4
1 5 9
2 6 5
9 7 3
3 4
3 1 2 40000
3 4 2 1
33 42 17 23