Transportation Optimization in W Country

W Country has a unique transportation network that forms a tree structure. There are n − 1 cities and n villages. The cities are numbered from 1 to n − 1 and the villages from 1 to n; city 1 is the capital. In the original network the roads are unidirectional and only roads from villages (or from a city with a larger number) lead to a city. More precisely, each city has exactly two incoming roads – one highway and one railway – while no road enters any village. Moreover, except for the capital, every city or village has exactly one outgoing road such that, starting from any village and following the unique outgoing road repeatedly, one can always reach the capital.

The king of W Country has a limited budget to refurbish exactly n − 1 roads. For each city, he must choose exactly one road from among the two (its highway or its railway) and refurbish it. Note that each city’s incoming road that is not refurbished remains unrefurbished. Although the refurbishment decisions do not affect the connectivity (each village still has a unique route to the capital), they affect the travel inconvenience.

For each village i (1 ≤ i ≤ n), three parameters a_i, b_i and c_i are provided based on a population survey. Suppose that on the unique path from village i to the capital, the number of unrefurbished highways is x and the number of unrefurbished railways is y. Then the inconvenience of village i is defined as

$$c_i\cdot\Bigl( a_i+x \Bigr)\cdot \Bigl( b_i+y \Bigr)$$

The total inconvenience for a given refurbishment scheme is the sum of the inconveniences of all villages. The goal is to choose a refurbishment scheme (i.e. for each city, select the road to refurbish) so that the total inconvenience is minimized.

Observation: The unique structure of the network ensures that each village’s route is fixed. Hence for every city, the road on the fixed route entering it (the connectivity road) is one of the two available. In an optimal scheme, it is always best to refurbish the connectivity road so that no additional unrefurbished road is encountered along the route. Therefore, the optimal total inconvenience equals

$$\sum_{i=1}^{n} c_i \cdot a_i\cdot b_i.$$

Your task is to compute this minimum total inconvenience value.

inputFormat

The first line contains an integer n (n ≥ 2).

The next n − 1 lines each contain two integers. For the i-th city (1 ≤ i ≤ n − 1), the two integers represent the starting nodes of the highway and the railway roads leading to that city. (Each starting node is either a village (numbered from 1 to n) or a city with a number greater than i.)

The following n lines each contain three integers: a_i, b_i and c_i for village i (1 ≤ i ≤ n).

You may assume that the input satisfies the conditions described in the problem statement.

outputFormat

Output a single integer – the minimum total inconvenience value.

sample

2
1 2
1 2 3
2 3 4

30