DZY loves planting, and he enjoys solving tree problems.

DZY has a weighted tree (connected undirected graph without cycles) containing n nodes (they are numbered from 1 to n). He defines the function g(x, y) (1 ≤ x, y ≤ n) as the longest edge in the shortest path between nodes x and y. Specially g(z, z) = 0 for every z.

For every integer sequence p₁, p₂, ..., p_n (1 ≤ p_i ≤ n), DZY defines f(p) as $\text{[math]}$ .

DZY wants to find such a sequence p that f(p) has maximum possible value. But there is one more restriction: the element j can appear in p at most x_j times.

Please, find the maximum possible f(p) under the described restrictions.

Input

The first line contains an integer n (1 ≤ n ≤ 3000).

Each of the next n - 1 lines contains three integers a_i, b_i, c_i (1 ≤ a_i, b_i ≤ n; 1 ≤ c_i ≤ 10000), denoting an edge between a_i and b_i with length c_i. It is guaranteed that these edges form a tree.

Each of the next n lines describes an element of sequence x. The j-th line contains an integer x_j (1 ≤ x_j ≤ n).

Output

Print a single integer representing the answer.

Note

In the first sample, one of the optimal p is [4, 3, 2, 1].

DZY Loves Planting

Examples