5 15
5 2 3
1 4 2
2 4 4
1 3 5
1 2 8
3 1 10
4 2 2
4 3 7
2 1 9
4 5 9
1 5 2
3 5 5
3 2 7
5 4 1
2 3 5