黑暗爆炸OJ

DARKBZOJ

#2725. [Violet 6]故乡的梦

Statistics 下载数据

Description

Input

Output

Sample 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

Sample Output

7
6
Infinity
7

Hint

Source

interviewstreet--Going office