Input
4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0
Output
7
Input
3 1
1 2 3
0
1 3
0
Output
-1