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