B'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, xe2 x80 x89y) (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89x, xe2 x80 x89y xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n) as the longest edge in the shortest path between nodes x and y. Specially g(z, xe2 x80 x89z) xe2 x80 x89= xe2 x80 x890 for every z. For every integer sequence p1, xe2 x80 x89p2, xe2 x80 x89..., xe2 x80 x89pn (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89pi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n), 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 xj times. Please, find the maximum possible f(p) under the described restrictions. The first line contains an integer n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x893000). Each of the next n xe2 x80 x89- xe2 x80 x891 lines contains three integers ai, xe2 x80 x89bi, xe2 x80 x89ci (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ai, xe2 x80 x89bi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n; 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ci xe2 x80 x89 xe2 x89 xa4 xe2 x80 x8910000), denoting an edge between ai and bi with length ci. 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 xj (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89xj xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n). Print a single integer representing the answer. In the first sample, one of the optimal p is [4, xe2 x80 x893, xe2 x80 x892, xe2 x80 x891].'...