Tree Shuffling

Description:

Input:

First line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ denoting the number of nodes in the tree.

$$$i$$$-th line of the next $$$n$$$ lines contains 3 space-separated integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ $$$(1 \leq a_i \leq 10^9, 0 \leq b_i, c_i \leq 1)$$$  — the cost of the $$$i$$$-th node, its initial digit and its goal digit.

Each of the next $$$n - 1$$$ lines contain two integers $$$u$$$, $$$v$$$ $$$(1 \leq u, v \leq n, \text{ } u \ne v)$$$, meaning that there is an edge between nodes $$$u$$$ and $$$v$$$ in the tree.

Output:

Print the minimum total cost to make every node reach its target digit, and $$$-1$$$ if it is impossible.

Sample Input:

5
1 0 1
20 1 0
300 0 1
4000 0 0
50000 1 0
1 2
2 3
2 4
1 5

Sample Output:

4

Sample Input:

5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5

Sample Output:

24000

Sample Input:

2
109 0 1
205 0 1
1 2

Sample Output:

-1

Note:

The tree corresponding to samples $$$1$$$ and $$$2$$$ are:

In sample $$$1$$$, we can choose node $$$1$$$ and $$$k = 4$$$ for a cost of $$$4 \cdot 1$$$ = $$$4$$$ and select nodes $$${1, 2, 3, 5}$$$, shuffle their digits and get the desired digits in every node.

In sample $$$2$$$, we can choose node $$$1$$$ and $$$k = 2$$$ for a cost of $$$10000 \cdot 2$$$, select nodes $$${1, 5}$$$ and exchange their digits, and similarly, choose node $$$2$$$ and $$$k = 2$$$ for a cost of $$$2000 \cdot 2$$$, select nodes $$${2, 3}$$$ and exchange their digits to get the desired digits in every node.

In sample $$$3$$$, it is impossible to get the desired digits, because there is no node with digit $$$1$$$ initially.