Problem Description

W国的交通 system is structured like a tree. W has $n-1$ cities and $n$ villages, with cities numbered from $1$ to $n-1$ and villages numbered from $1$ to $n$, where city $1$ is the capital. All roads are one-way, and we only consider the road network from villages to the capital.

Each city has exactly one road and one railway leading to it. For city $i$, the starting point of the road or railway leading to it is either a village or a city with a number greater than $i$. No roads lead to any village. Except for the capital, each city or village has only one outgoing road; the capital has no outgoing roads. Starting from any village, following the only outgoing road will eventually lead to the capital.

King Xiao W of W has received a fund to improve the transportation. Due to limited funds, Xiao W can only renovate $n-1$ roads. He decides to renovate exactly one road leading to each city, choosing either the road or the railway. Xiao W wants the transportation from villages to cities to be as convenient as possible. Based on population data, Xiao W has set three parameters for each village. For village $i$, the parameters are $a_i$, $b_i$, and $c_i$. If it takes $x$ unrenovated roads and $y$ unrenovated railways to travel from village $i$ to the capital, the inconvenience value of the village is:

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

The sum of the inconvenience values of all villages under a given renovation plan is the inconvenience value of that plan. There are many renovation plans, and the one with the smallest inconvenience value is considered the optimal plan. Xiao W wants to find the optimal plan and asks you to help him calculate the minimum inconvenience value.

Input Format

The first line contains a positive integer $n$.

The next $n - 1$ lines describe the cities. Each line contains two numbers $s_i$ and $t_i$. $s_i$ represents the starting point of the road leading to city $i$, and $t_i$ represents the starting point of the railway leading to city $i$. If $s_i > 0$, there is a road from city $s_i$ to city $i$; otherwise, there is a road from village $-s_i$ to city $i$. $t_i$ is similar, where if $t_i > 0$, there is a railway from city $t_i$ to city $i$; otherwise, there is a railway from village $-t_i$ to city $i$.

The next $n$ lines describe the villages. Each line contains three numbers $a_i$, $b_i$, and $c_i$, as described in the problem statement.

Output Format

Output a single integer, the minimum inconvenience value of the optimal renovation plan.

Sample Input and Output

Input Sample #1

6
2 3
4 5
-1 -2
-3 -4
-5 -6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Output Sample #1

54

Input Sample #2

9
2 -2
3 -3
4 -4
5 -5
6 -6
7 -7
8 -8
-1 -9
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1

Output Sample #2

548

Input Sample #3

12
2 4
5 3
-7 10
11 9
-1 6
8 7
-6 -10
-9 -4
-12 -5
-2 -3
-8 -11
53 26 491
24 58 190
17 37 356
15 51 997
30 19 398
3 45 27
52 55 838
16 18 931
58 24 212
43 25 198
54 15 172
34 5 524

Output Sample #3

5744902

Notes/Hints

For a total of 20 test cases, numbered 1 to 20.

For cases numbered $\leq 4$, $n \leq 20$;
For cases numbered 5 to 8, $a_i, b_i, c_i \leq 5$, $n \leq 50$;
For cases numbered 9 to 12, $n \leq 2000$;
For all cases, $n \leq 20000$, $1 \leq a_i, b_i \leq 60$, $1 \leq c_i \leq 10^9$, $s_i, t_i$ are integers within $[-n, -1] \cup (i, n - 1]$, and any village can reach the capital via no more than 40 roads.

见题面 Input 部分

见题面 Output 部分