CF444E.DZY Loves Planting

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_1, _p_2, ..., p__n (1 ≤ p__i ≤ n), DZY defines f(p) as .

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.

DZY 喜欢种植，也喜欢解决树上的问题。

DZY 有一棵带权树（即无环的连通无向图），包含 $ n $ 个节点（编号为 $ 1 $ 到 $ n $）。他定义函数 $ g(x, y) $（其中 $ 1 \le x, y \le n $）为节点 $ x $ 与 $ y $ 之间最短路径上边权的最大值。特别地，对任意 $ z $，定义 $ g(z, z) = 0 $。

对于任意整数序列 $ p_1, p_2, \dots, p_n $（其中 $ 1 \le p_i \le n $），DZY 定义 $ f(p) $ 为
。

DZY 希望找到一个序列 $ p $，使得 $ f(p) $ 的值尽可能大。但还有一个额外限制：元素 $ j $ 在序列 $ p $ 中至多可出现 $ x_j $ 次。

请在上述限制条件下，求出 $ f(p) $ 的最大可能值。

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).

第一行包含一个整数 $n$（$1 \leq n \leq 3000$）。

接下来的 $n-1$ 行中，每行包含三个整数 $a_i,\, b_i,\, c_i$（$1 \leq a_i,\, b_i \leq n$；$1 \leq c_i \leq 10000$），表示一条连接顶点 $a_i$ 与 $b_i$、长度为 $c_i$ 的边。保证这些边构成一棵树。

接下来的 $n$ 行描述序列 $x$ 的各个元素。第 $j$ 行包含一个整数 $x_j$（$1 \leq x_j \leq n$）。

Print a single integer representing the answer.

输出一个整数，表示答案。

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

在第一个样例中，一个最优的 $p$ 是 [4, 3, 2, 1]。