输入样例

5 
2 3 4 
1 2 1 
4 1 2 
2 1 1 
3 2 3 
5 
1 10 
2 7 
3 4 
4 8 
0 5 

Output

6 
7 
5 
6 
4 

Limitation

1s, 512MiB for each test case.