Input 
1
5 5 3
1 2 2
2 3 3
3 4 1
4 5 1
5 1 3
3
2
1
Output 
2
6
10