human
Ashish has a tree consisting of n nodes numbered 1 to n rooted at node 1. The i-th node in the tree has a cost a_i, and binary digit b_i is written in it. He wants to have binary digit c_i written in the i-th node in the end.

To achieve this, he can perform the following operation any number of times: 

  * Select any k nodes from the subtree of any node u, and shuffle the digits in these nodes as he wishes, incurring a cost of k ⋅ a_u. Here, he can choose k ranging from 1 to the size of the subtree of u. 


He wants to perform the operations in such a way that every node finally has the digit corresponding to its target.

Help him find the minimum total cost he needs to spend so that after all the operations, every node u has digit c_u written in it, or determine that it is impossible.

Input

First line contains a single integer n (1 ≤ n ≤ 2 ⋅ 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 ≤ a_i ≤ 10^9, 0 ≤ b_i, c_i ≤ 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 ≤ u, v ≤ n,   u ≠ 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.

Examples

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

Output

4

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

Output

24000

Input

2
109 0 1
205 0 1
1 2

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 ⋅ 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 ⋅ 2, select nodes {1, 5} and exchange their digits, and similarly, choose node 2 and k = 2 for a cost of 2000 ⋅ 2, select nodes {2, 3} and exchange their digits to get the desired digits...
Using python3 can you solve the prior task?
assistant
#Here is Python code to find the minimum total cost he needs to spend so that after all the operations, every node u has digit c_u written in it, or determine that it is impossible.


# from math import factorial as fac
from collections import defaultdict
# from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
# print(f.readline())

	
def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline().strip())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())
def bi(x):
	return bin(x)[2:]



from collections import deque
import math

from collections import deque, defaultdict 
import heapq
from sys import stdout

#	a=cost, b=written, c=wanted 
import threading
from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to

    return wrappedfunc

# sys.setrecursionlimit(2*10**5+2)
# # sys.setrecursionlimit(10**6)
# threading.stack_size(10**8)
@bootstrap
def dfs(v,adj,curr_min,visited,data,res):
	visited[v] = True
	curr_min = min(curr_min,data[v][0])
	balance = data[v][2]-data[v][1]
	total = abs(balance)
	for u in adj[v]:
		if visited[u]:
			continue
		zeros = yield dfs(u,adj,curr_min,visited,data,res)
		balance += zeros
		total += abs(zeros)
	res[0] += curr_min * (total-abs(balance))
	yield balance

def...