Conquer the World

Time limit: 8 seconds

Bwahahahahaha!!! Your nemesis, the dashingly handsome spy WacoPowers, has at last fallen to your secret volcano base’s deathtraps(or so you assume, being a little too busy to witness itfirsthand). At long last, you are all set to CONQUER THE WORLD!

Nothing will stand in your way! Well, nothing except a minorproblem of logistics. Your evil armies have announced that theywill not continue carving their relentless path of destructionacross the puny nations of the world without being paid. Andunfortunately you are running low on cash – a volcano lair has manywonderful qualities, but “reasonably affordable” is not one ofthem. You have had to pull funds from the travel budget to pay yourungrateful underlings. Now you are not sure how you will actuallyget your armies into position to CONQUER THE WORLD.

You have a map of the nations of the world and all youravailable transport routes between them. Each route connects twonations and has a fixed cost per army that uses it. The routes arelaid out such that there is exactly one way to travel between anytwo nations. You know the current position of each of your armiesand how many you will need to place permanently in each nation inorder to subjugate it. How can you move the armies into place ascheaply as possible so you can CONQUER THE WORlD?

Input

The first line of input contains an integer n (1 ≤n ≤ 250000), the number of nations. This is followed byn − 1 lines, each containing three integers u,v, and c (1 ≤ u,v ≤ n, 1 ≤c ≤ 10⁶), indicating that there is abidirectional route connecting nations u and v,which costs c per army to use.

Finally, another n lines follow, thei^th of which contains two non-negative integersx_i and y_i, indicating thatthere are currently x_i armies in nationi, and you need at least y_i armies toend up in that nation in the final configuration. The total numberof armies (the sum of the x_i values) is atleast the sum of the y_i values, and no morethan 10⁶.

Output

Display the minimum cost to move your armies such that there areat least y_i armies in nation i for alli.

Sample Input1                                                     Sample Output 1

3 1 2 5 3 1 5 2 1 5 0 1 3

15

Sample Input 2 Sample Output 2

6 1 2 2 1 3 5 1 4 1 2 5 5 2 6 1 0 0 1 0 2 1 2 1 0 1 0 1

9

Q:What is Actually asked in the problem briefly define theproblem and give its solution?