CF444E DZY Loves Planting

给出一个 $n$ 个点的带边权的树。 定义 $g(x,y)\,(1\leq x,y\leq n)$ 为 $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\,(1\leq n\leq 3000)$。 接下来一共 $n-1$ 行，每行三个数 $u,v,w\,(1\leq u,v\leq n; 1\leq w\leq 10000)$ ，表示一条 $u,v$ 之间权值为 $w$ 的边。 最后一行，一共 $n$ 个数，表示 $x_i\,(1\leq x_i\leq n)$。

一个数，表示 $f(P)$ 的最大值。

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