The architectural structure of the college is strange, but the rule is that there is only one simple path between every two classrooms. Now the battle between Class A and Class F broke out. As a support staff of Class F, you have to go to every fight in time to help out. With the help of icebound, Class F know the probability of each classroom being attacked. So we define an important degree for each classroom. Now ask you to find a classroom xin nclassrooms as your resting ba se which has the minimum F(x). F(x) = ∑ w(i) × d(x, i), dis the distance between xand i.

he first line is an integer n，which is the number of classrooms.
Then n-1lines follow. Each line has three numbers x,y,z. There is a road of zmeters between xand y.
The last line contains nnumbers. The i‑th number w(i)is the important degree of the classroom.
2 ≤ n ≤ 5 × 10⁵, 0 ≤ z, wi ≤ 1000,1 ≤ x, y ≤ n

Output a line with an integer, representing the minimum F(x).

2018CCPC河北省赛