Input
3 3
1 2 1
2 3 1
3 1 1
Output
1
Input
3 3
1 2 1
2 3 2
3 1 3
Output
3
Input
6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4
Output
6