营养快线

内存限制: 128M   时间限制: 1S

题目描述


输入

输出

样例输入

4 3	
1 2 4
2 3 3
3 1 1
3		
1 3	
1 4	
1 3	

样例输出

3
-1
3