Input
4 5
1 3 4
1 2 5
5 6 1
1 2 4
Output
5
Input
3 2
4 6 3
2 4 1
3 5 4
Output
-1