3 6
3 1
1 2 1
2 3 1
3 2 1
2 1 1
1 3 4
3 1 4
3 6
5 1 
1 2 1
2 3 1
3 2 1
2 1 1
1 3 4
3 1 4
4 5 
3 1 
3 1 
1 2 5
2 3 5
3 4 5
4 2 5
3 1 5
2 1
2 1 1
0 0

7
8
36
-1