Input
3 0
Output
4
Input
4 4
1 2 1
2 3 1
3 4 0
4 1 0
Output
1
Input
4 4
1 2 1
2 3 1
3 4 0
4 1 1
Output
0