5 2
1 3
1 2 1
3 4 2
5 5 3
1 5
2 1
1 4 4
1 5