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, typename U>
inline void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void amax(T &x, U y) {
  if (x < y) x = y;
}
struct UnionFind {
  vector<int> data;
  void init(int n) { data.assign(n, -1); }
  bool unionSet(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};
struct MaximumFlow {
  static const int InfCapacity = 0x3f3f3f3f;
  struct Edge {
    int to;
    int capacity;
    int rev;
  };
  vector<vector<Edge> > g;
  void init(int n) { g.assign(n, vector<Edge>()); }
  void add(int i, int j, int capacity) {
    Edge e, f;
    e.to = j, f.to = i;
    e.capacity = capacity, f.capacity = 0;
    g[i].push_back(e);
    g[j].push_back(f);
    g[i].back().rev = (int)g[j].size() - 1;
    g[j].back().rev = (int)g[i].size() - 1;
  }
  void addB(int i, int j, int capacity) {
    Edge e, f;
    e.to = j, f.to = i;
    e.capacity = capacity, f.capacity = capacity;
    g[i].push_back(e);
    g[j].push_back(f);
    g[i].back().rev = (int)g[j].size() - 1;
    g[j].back().rev = (int)g[i].size() - 1;
  }
  int maximumFlow(int s, int t) {
    int n = g.size();
    vector<int> level(n);
    int total = 0;
    bool update;
    do {
      update = false;
      fill(level.begin(), level.end(), -1);
      level[s] = 0;
      queue<int> q;
      q.push(s);
      for (int d = n; !q.empty() && level[q.front()] < d;) {
        int u = q.front();
        q.pop();
        if (u == t) d = level[u];
        for (typeof((g[u]).begin()) e = ((g[u]).begin()); e != (g[u]).end();
             ++e)
          if (e->capacity > 0 && level[e->to] == -1)
            q.push(e->to), level[e->to] = level[u] + 1;
      }
      vector<int> iter(n);
      for (int i = 0; i < n; i++) iter[i] = (int)g[i].size() - 1;
      while (1) {
        int f = augment(level, iter, s, t, InfCapacity);
        if (f == 0) break;
        total += f;
        update = true;
      }
    } while (update);
    return total;
  }
  int augment(vector<int> &level, vector<int> &iter, int u, int t, int f) {
    if (u == t || f == 0) return f;
    int lv = level[u];
    if (lv == -1) return 0;
    level[u] = -1;
    for (; iter[u] >= 0; --iter[u]) {
      Edge &e = g[u][iter[u]];
      if (level[e.to] <= lv) continue;
      int l = augment(level, iter, e.to, t, min(f, e.capacity));
      if (l == 0) continue;
      e.capacity -= l;
      g[e.to][e.rev].capacity += l;
      level[u] = lv;
      return l;
    }
    return 0;
  }
};
int main() {
  int n;
  scanf("%d", &n);
  vector<pair<pair<int, int>, int> > edges;
  for (int(i) = 0; (i) < (int)(n - 1); ++(i)) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c), a--, b--;
    edges.push_back(make_pair((make_pair((a), (b))), (c)));
  }
  vector<int> x(n);
  for (int(i) = 0; (i) < (int)(n); ++(i)) scanf("%d", &x[i]);
  int l = 0, u = 10000;
  while (u - l > 0) {
    int mid = (l + u + 1) / 2;
    UnionFind uf;
    uf.init(n);
    for (int(i) = 0; (i) < (int)(n - 1); ++(i))
      if (edges[i].second < mid)
        uf.unionSet(edges[i].first.first, edges[i].first.second);
    vector<vector<int> > components(n);
    for (int(i) = 0; (i) < (int)(n); ++(i)) components[uf.root(i)].push_back(i);
    vector<int> componentList;
    for (int(i) = 0; (i) < (int)(n); ++(i))
      if (!components[i].empty()) componentList.push_back(i);
    int C = componentList.size();
    int B = max(1, (int)pow(C, .5)), Buckets = (C + B - 1) / B;
    int s = C + Buckets + C, t = s + 1;
    MaximumFlow mf;
    mf.init(t + 1);
    for (int(i) = 0; (i) < (int)(C); ++(i)) {
      int cs = components[componentList[i]].size();
      mf.add(s, i, cs);
      for (int(j) = 0; (j) < (int)(Buckets); ++(j)) {
        int L = j * B, R = min(C, (j + 1) * B);
        if (i < L || R <= i) {
          mf.add(i, C + j, cs);
        } else {
          for (int(k) = (int)(L); (k) < (int)(R); ++(k))
            if (i != k) mf.add(i, C + Buckets + k, cs);
        }
      }
    }
    for (int(j) = 0; (j) < (int)(Buckets); ++(j)) {
      int L = j * B, R = min(C, (j + 1) * B);
      for (int(k) = (int)(L); (k) < (int)(R); ++(k))
        mf.add(C + j, C + Buckets + k, 0x3f3f3f3f);
    }
    for (int(i) = 0; (i) < (int)(C); ++(i)) {
      int cap = 0;
      for (typeof((components[componentList[i]]).begin()) j =
               ((components[componentList[i]]).begin());
           j != (components[componentList[i]]).end(); ++j)
        cap += x[*j];
      mf.add(C + Buckets + i, t, cap);
    }
    int f = mf.maximumFlow(s, t);
    if (f == n)
      l = mid;
    else
      u = mid - 1;
  }
  printf("%d\n", l);
  return 0;
}