Cow Gathering

Bessie is planning the annual cow gathering. There are (N) farms connected by (N-1) roads such that there is a unique path between any two farms (i.e. the farms form a tree). Road (i) connects farm (A_i) and farm (B_i) with length (L_i). Farm (i) houses (C_i) cows. The gathering can be held at any farm. If the meeting is held at farm (X), the inconvenience is calculated as the sum over all farms (i) ((i \neq X)) of (C_i \times d(i, X)), where (d(i, X)) is the distance from farm (i) to farm (X).

Your task is to choose the farm that minimizes the total inconvenience and output this minimum inconvenience value.

inputFormat

The first line contains a single integer (N) ((1 \leq N \leq 10^5)) representing the number of farms. The following (N-1) lines each contain three integers (A_i), (B_i), and (L_i) ((1 \leq A_i, B_i \leq N); (1 \leq L_i \leq 10^9)), describing a road between farms (A_i) and (B_i) with length (L_i). The last line contains (N) integers (C_1, C_2, \ldots, C_N) ((0 \leq C_i \leq 10^9)) where (C_i) denotes the number of cows at farm (i).

outputFormat

Output a single integer which is the minimum total inconvenience achievable.

sample

3
1 2 1
2 3 2
3 2 1

5