[Violet 6]故乡的梦

时间限制:20s    【提交】    空间限制:128MB

题目描述


输入格式


输出格式


样例输入

6 7 
1 2 1 
2 3 1 
3 4 2 
4 5 1 
5 6 1 
1 3 3 
4 6 3 
1 6 
4 
1 2 
1 3 
4 3 
6 5 

样例输出

7
6
Infinity
7

提示


题目来源

interviewstreet--Going office