2725 - [Violet 6]故乡的梦

Input

Output

Examples

Input

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

Output

7
6
Infinity
7
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题