6 7
60000
1 1 1
3 1 2
5 1 2
1 3 4
3 3 4
5 3 3
1 4 1
3 4 1
5 4 2
1 6 4
3 6 3
5 6 3
2 5 4