tree

题目描述

给出一个 $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)$ 的最大值。

样例

输入

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

输出

2

数据范围

$1 \leq n \leq 100000, 1 \leq w \leq 10^9, 1 \leq x_i \leq n$。

Subtask1 ($30\%$) ： $n \leq 10$ 。

Subtask2 ($30\%$) ： $n \leq 1000$ 。

Subtask3 ($40\%$) ：无特殊限制。

时间限制： $1s$ 。

空间限制： $256MB$ 。