Problem: 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 p1, p2, ..., pn (1 ≤ pi ≤ n), DZY defines f(p) as <image>. 

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.

Input

The first line contains an integer n (1 ≤ n ≤ 3000).

Each of the next n - 1 lines contains three integers ai, bi, ci (1 ≤ ai, bi ≤ n; 1 ≤ ci ≤ 10000), 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 ≤ xj ≤ n).

Output

Print a single integer representing the answer.

Examples

Input

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


Output

2


Input

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


Output

3

Note

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline int len(const T &a) {
  return a.size();
}
constexpr int mxn = 3e3 + 10;
int n, p[mxn];
tuple<int, int, int> edges[mxn];
int guys[mxn], psum[mxn];
void clear() {
  for (int i = 0; i < mxn; ++i) {
    guys[i] = -1;
    psum[i] = p[i];
  }
}
int root(int v) { return guys[v] < 0 ? v : guys[v] = root(guys[v]); }
void unite(int v, int u) {
  v = root(v), u = root(u);
  if (v == u) {
    return;
  }
  if (guys[u] < guys[v]) {
    swap(u, v);
  }
  guys[v] += guys[u];
  guys[u] = v;
  psum[v] += psum[u];
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n - 1; ++i) {
    int v, u, w;
    scanf("%d%d%d", &v, &u, &w);
    edges[i] = {w, --v, --u};
  }
  int allp = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &p[i]);
    allp += p[i];
  }
  auto solve = [&](int mid) {
    clear();
    for (int i = 0; i < n - 1; ++i) {
      if (get<0>(edges[i]) < mid) {
        unite(get<1>(edges[i]), get<2>(edges[i]));
      }
    }
    for (int i = 0; i < n; ++i) {
      if (guys[i] >= 0) {
        continue;
      }
      if (-guys[i] > (allp - psum[i])) {
        return false;
      }
    }
    return true;
  };
  int low = 0, high = 10000;
  while (high - low > 0) {
    int mid = (high + low + 1) >> 1;
    if (solve(mid)) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  printf("%d", low);
  return 0;
}