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;
inline int read() {
  int x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') positive = 0;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
const int N = 3005 * 4, inf = 1 << 28;
int n, l, S = 0, T = 1, p[N], c[N], x[N], y[N], z[N], xx[N], yy[N], ed[N * 8],
          data[N * 8], Next[N * 8], son[N], d[N], f[N];
bool cmp(const int i, const int j) { return z[i] < z[j]; }
void add(int x, int y, int z) {
  ed[++l] = y, data[l] = z, Next[l] = son[x], son[x] = l;
  ed[++l] = x, data[l] = 0, Next[l] = son[y], son[y] = l;
}
int get(int x) { return f[x] == x ? x : f[x] = get(f[x]); }
bool build() {
  int h = 0, t = 1;
  memset(d, -1, sizeof(d)), d[f[1] = S] = 0;
  while (h < t) {
    int x = f[++h];
    for (int y, p = son[x]; p; p = Next[p])
      if (data[p]) {
        if (d[y = ed[p]] < 0) d[y] = d[x] + 1, f[++t] = y;
        if (y == T) return 1;
      }
  }
  return 0;
}
int dinic(int x, int low) {
  if (x == T) return low;
  int w = 0, res;
  for (int y, p = son[x]; p; p = Next[p])
    if (data[p] && d[y = ed[p]] == d[x] + 1)
      if (res = dinic(y, min(low - w, data[p])))
        data[p] -= res, data[p ^ 1] += res, w += res;
  if (!w) d[x] = -1;
  return w;
}
int work() {
  int Z = n, ans = 0;
  memset(son, 0, sizeof(son)), l = 1;
  for (int i = 1; i <= n; ++i)
    add(S, i * 2, 1), add(i * 2 + 1, T, c[i]), f[i] = i;
  for (int i = 1; i <= n - 1; ++i) {
    int X = get(x[p[i]]), Y = get(y[p[i]]);
    f[++Z] = Z, xx[i] = X, yy[i] = Y;
    f[X] = Z, f[Y] = Z;
    add(X * 2, Z * 2, inf), add(Y * 2, Z * 2, inf);
    add(Z * 2 + 1, X * 2 + 1, inf), add(Z * 2 + 1, Y * 2 + 1, inf);
  }
  for (int i = n - 1; i; --i) {
    int X = xx[i], Y = yy[i];
    add(X * 2, Y * 2 + 1, inf), add(Y * 2, X * 2 + 1, inf);
    while (build()) ans += dinic(S, inf);
    if (ans == n) return z[p[i]];
  }
}
int main() {
  n = read();
  if (n == 1) {
    printf("%d\n", 0);
    return 0;
  }
  for (int i = 1; i <= n - 1; ++i)
    x[i] = read(), y[i] = read(), z[i] = read(), p[i] = i;
  for (int i = 1; i <= n; ++i) c[i] = read();
  sort(p + 1, p + n, cmp);
  printf("%d\n", work());
  return 0;
}