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>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cout << *i << " ";
  cout << endl;
}
template <typename T>
void chmin(T &t, const T &f) {
  if (t > f) t = f;
}
template <typename T>
void chmax(T &t, const T &f) {
  if (t < f) t = f;
}
int in() {
  int x;
  scanf("%d", &x);
  return x;
}
namespace MF {
const int LIM_N = 6005;
const int LIM_M = 10000005;
const int wEPS = 0;
const int wINF = 1001001001;
int n, m, ptr[LIM_N], nxt[LIM_M * 2], zu[LIM_M * 2];
int capa[LIM_M * 2], tof;
int lev[LIM_N], see[LIM_N], que[LIM_N], *qb, *qe;
void init(int _n) {
  n = _n;
  m = 0;
  fill(ptr, ptr + n, -1);
}
void ae(int u, int v, int w0, int w1 = 0) {
  nxt[m] = ptr[u];
  ptr[u] = m;
  zu[m] = v;
  capa[m] = w0;
  ++m;
  nxt[m] = ptr[v];
  ptr[v] = m;
  zu[m] = u;
  capa[m] = w1;
  ++m;
}
int augment(int src, int ink, int flo) {
  if (src == ink) return flo;
  for (int &i = see[src]; ~i; i = nxt[i])
    if (capa[i] > wEPS && lev[src] < lev[zu[i]]) {
      const int f = augment(zu[i], ink, min(flo, capa[i]));
      if (f > wEPS) {
        capa[i] -= f;
        capa[i ^ 1] += f;
        return f;
      }
    }
  return 0;
}
bool solve(int src, int ink, int flo = wINF) {
  for (tof = 0; tof + wEPS < flo;) {
    qb = qe = que;
    fill(lev, lev + n, -1);
    for (lev[ *qe++ = src] = 0, see[src] = ptr[src]; qb != qe;) {
      const int u = *qb++;
      for (int i = ptr[u]; ~i; i = nxt[i])
        if (capa[i] > wEPS) {
          const int v = zu[i];
          if (lev[v] == -1) {
            lev[ *qe++ = v] = lev[u] + 1;
            see[v] = ptr[v];
            if (v == ink) goto au;
          }
        }
    }
    return false;
  au:
    for (int f; (f = augment(src, ink, flo - tof)) > wEPS; tof += f)
      ;
  }
  return true;
}
}  // namespace MF
int uf[3010];
int root(int u) { return (uf[u] < 0) ? u : (uf[u] = root(uf[u])); }
void conn(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
}
int N;
int A[3010], B[3010], C[3010];
int X[3010];
int numCompos;
int us[3010];
int ids[3010];
int sumX[3010];
bool check(int threshold) {
  fill(uf, uf + N, -1);
  for (int i = 0; i < N - 1; ++i) {
    if (C[i] < threshold) {
      conn(A[i], B[i]);
    }
  }
  numCompos = 0;
  for (int u = 0; u < N; ++u)
    if (uf[u] < 0) {
      us[numCompos] = u;
      ids[u] = numCompos++;
    }
  fill(sumX, sumX + numCompos, 0);
  for (int u = 0; u < N; ++u) {
    chmin(sumX[ids[root(u)]] += X[u], N);
  }
  MF::init(2 + numCompos + numCompos);
  for (int a = 0; a < numCompos; ++a) {
    MF::ae(0, 2 + a, -uf[us[a]]);
    MF::ae(2 + numCompos + a, 1, sumX[a]);
  }
  for (int a = 0; a < numCompos; ++a)
    for (int b = 0; b < numCompos; ++b)
      if (a != b) {
        MF::ae(2 + a, 2 + numCompos + b, -uf[us[a]]);
      }
  const bool res = MF::solve(0, 1, N);
  return res;
}
int csLen;
int cs[3010];
int main() {
  for (; ~scanf("%d", &N);) {
    for (int i = 0; i < N - 1; ++i) {
      A[i] = in() - 1;
      B[i] = in() - 1;
      C[i] = in();
    }
    for (int u = 0; u < N; ++u) {
      X[u] = in();
    }
    copy(C, C + N - 1, cs);
    sort(cs, cs + N - 1);
    csLen = unique(cs, cs + N - 1) - cs;
    int lo = 0, ho = csLen;
    for (; lo + 1 < ho;) {
      const int mo = (lo + ho) / 2;
      (check(cs[mo]) ? lo : ho) = mo;
    }
    printf("%d\n", cs[lo]);
  }
  return 0;
}