输入样例1

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

输出样例1

8 
9 
10 
10 

输入样例2

4 3 1 
1 2 7 
1 3 4 
2 3 
9 

输出样例2

+Inf

Limitation

1s, 256MiB for each test case.