5 22
1 2 1
2 3 1
1 3 1
3 5 2
2 5 2
1 5 2
1 2 3
5 3 3
5 3 4
4 5 4
2 3 5
2 4 5
4 1 6
4 1 6
3 4 7
2 3 7
1 2 8
2 5 8
5 2 8
2 4 9
4 5 9
4 1 10
1 3 10