Description

Country Z has N cities, which are numbered from 1 to N. Cities are connected by highways, and there is exact one path between two different cities. Recently country Z often caught fire, so the government decided to build some firehouses in some cities. Build a firehouse in city K cost W(K). W for different cities may be different. If there is not firehouse in city K, the distance between it and the nearest city which has a firehouse, can’t be more than D(K). D for different cities also may be different. To save money, the government wants you to calculate the minimum cost to build firehouses.

Input

The first line of input contains a single integer T representing the number of test cases. The following T blocks each represents a test case.

The first line of each block contains an integer N (1 < N <= 1000). The second line contains N numbers separated by one or more blanks. The I-th number means W(I) (0 < W(I) <= 10000). The third line contains N numbers separated by one or more blanks. The I-th number means D(I) (0 <= D(I) <= 10000). The following N-1 lines each contains three integers u, v, L (1 <= u, v <= N，0 < L <= 1000), which means there is a highway between city u and v of length L.

Output

For each test case output the minimum cost on a single line.

5
5
1 1 1 1 1
1 1 1 1 1
1 2 1
2 3 1
3 4 1
4 5 1
5
1 1 1 1 1
2 1 1 1 2
1 2 1
2 3 1
3 4 1
4 5 1
5
1 1 3 1 1
2 1 1 1 2
1 2 1
2 3 1
3 4 1
4 5 1
4
2 1 1 1
3 4 3 2
1 2 3
1 3 3
1 4 2
4
4 1 1 1
3 4 3 2
1 2 3
1 3 3
1 4 2

2
1
2
2
3

Source

POJ Monthly,Lou Tiancheng