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.

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