Lumberjack villages

Midgard has n villages connected by a network of roads. There are n - 1 roads in Midgard, and along these roads you can get from any village to any other. In other words, the road network forms a tree. Village number 1 is the capital. The Midgardians produce a lot of wood, from which they then build ships. Now the ruler of Midgard wants to build a large fleet in a year and set off to conquer new lands and resources. To do this, he decided to apply the following strategy:

Send governors to some villages. Moreover, on a simple path from the village to which the governor was sent to the capital, there should not be another village to which the governor was also sent. Please note that you can send one governor to the capital, but in this case you cannot send the governor to any other village.

The governor in the village v is given control over all the villages, from which the village v is located on a simple path to the capital. The village v is given also to the governor.

For each village, the value a[i] is known - the number of ships that this village will build in a year if it is not subordinate to any governor.

If there is a governor in the village v, then he acts as follows:

• He selects a subset of W villages adjacent to v that are under his control. In these villages, he develops large workshops for the production of ships. For each village, it is known that if a workshop is built in it, then timber from b[i] other villages must be supplied to this village, and this workshop will produce c[i] ships in a year.

• Now he must choose exactly Σ b[u] (u ∈ W) villages from the remaining villages under his control, which will supply wood to the workshops. To which particular workshop each of them will supply wood is not so important.

• The village i where the workshop is built will build c[i] ships in a year.

• A village that supplies wood will not build ships.

• All other villages under his control will build as many ships in a year as if they were not under his control. That is, the i-th village will build a[i] ships in a year.

The ruler can send out any number of governors. Assuming that the governors operate optimally, determine the maximum number of ships that can be built by all villages in a year.

Input

The first line contains one integer t (1 ≤ t ≤ 5000) - the number of tests. It is followed by t tests.

Each test starts with one integer n (1 ≤ n ≤ 5000) - the number of villages in Midgard.

The next n lines contain three integers a[i], b[i] and c[i] (1 ≤ a[i], c[ i] ≤ 10^9, 1 ≤ b[i] ≤ n) - the number of ships that the village will build in a year, not being subordinate to the governor, the number of villages that must supply timber to that village if a workshop is built in it, and the number of ships that the village will build in a year if a workshop is built in it.

The following n - 1 lines contain descriptions of roads in Midgard. Each line contains two integers v[i], u[i] - the numbers of the villages connected by the road. It is guaranteed that the road network forms a tree.

It is guaranteed that the sum of n in all tests does not exceed 5000.

Output

For each test, print one integer - the maximum number of ships that all villages can build in total in a year with the correct distribution of governors.

Examples