The Budget of Traveler

There is a country consisting of n cities. A traveler living in the city with number 1 loves travelling very much. He has made
n-1 travel plans, each plan has a unique destination(except city 1). After a travel, he will go back home. On the way back home,
he will buy gifts for all his friends living in the cities(including the starting city and ending city) he will pass. For some
strange reasons, each city sells only one kind gift. Besides, packing the gifts need some extra cost.
Maybe you are still confused of the description, the following is the details
1. Note that the cities form a connected, undirected and a cyclic graph(in another word the cities form a tree).
2. When he goes back home after a travel, he will always choose the shortest route.
3. The n-1 plans are independent, that means, he will always prepare gifts for his friends ont the route no matter whether he has visited them before.
4. The gifts must be packed, and you must pack them in the city where you buy them.
5. The packing cost is no matter with the number of gifts. That is, packing two gifts cost the same money with packing one.

The first line of the input contains an integer T( T<= 10 ), indicating the number of test cases.
For each test case, the first line contains only one integers n, indicating the number of cities.
The next n lines, each line contains three integers f_i, p_i, r_i, where f_i is the number of his friend living in city i, p_i is the price of each gift in city i, r_i is the packing cost in the city i.
The next of n-1 lines, each line contains two integers u_i and v_i, indicating that the traveler can go to v_i from u_i or go to u_i from v_i.
You can assume 1<=n<=4*10⁵, 1<=f_i<=10⁴, 1<=p_i,r_i<=10⁵, 1<=u_i,v_i<=n

For every test case,output one line,"Case #k: ans",where k is the case number,counting from 1, ans is the minimum total cost.

1
3
1 10000 10000
1 1 20
1 100 1
1 2
1 3

Case #1: 223

2013 Multi-University Training Contest 8