DZY Loves Planting

### 题目描述 给出一个 $n$ 个点的带边权的树。 定义 $g(x,y)$ 为 $x, y$ 两点路径上权值最大边的权值，并且如果 $x=y$ 则 $g(x,y)=0$ 。 对于一个长度为 $n$ 的序列 $P=\{p_1,p_2, \dots , p_n\},(1 \leq p_i \leq n)$ ，定义 $f(P)=\min\limits_{i=1}^n g(i,p_i)$。 如果一个序列 $P$ 是合法的，当且仅当元素 $j$ 在序列 $P$ 中出现的次数不超过 $x_j$ 次。 求所有合法的序列 $P$ 中， $f(P)$ 的最大值。 ### 输入格式 第一行一个数 $n$。 接下来一共 $n-1$ 行，每行三个数 $u,v,w$ ，表示一条 $u,v$ 之间权值为 $w$ 的边。 最后一行，一共$n$个数，表示 $x_i$。 ### 输出格式 一个数，表示 $f(P)$ 的最大值。

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.

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

Print a single integer representing the answer.

4
1 2 1
2 3 2
3 4 3
1
1
1
1

2

4
1 2 1
2 3 2
3 4 3
4
4
4
4

3

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