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;
const int maxn = 100005;
int n;
struct Edge2 {
  int from, to, dist, id;
  inline bool operator<(const Edge2& other) const {
    return this->dist > other.dist;
  }
} E[maxn];
struct Edge {
  int to, nxt, dist;
  bool flag;
} e[maxn << 1];
int first[maxn];
inline void add_edge(Edge2& ee) {
  static int cnt = 0;
  ee.id = ++cnt;
  e[cnt].nxt = first[ee.from];
  e[cnt].flag = false;
  first[ee.from] = cnt;
  e[cnt].to = ee.to;
  e[cnt].dist = ee.dist;
  e[++cnt].nxt = first[ee.to];
  e[cnt].flag = false;
  first[ee.to] = cnt;
  e[cnt].to = ee.from;
  e[cnt].dist = ee.dist;
}
int siz[maxn];
int xx[maxn];
long long sum_all;
long long sumx[maxn];
bool fff[maxn];
inline bool dfs(int now, int fa) {
  sumx[now] = xx[now];
  siz[now] = 1;
  for (int i = first[now]; i; i = e[i].nxt) {
    int to = e[i].to;
    if (to != fa) {
      if (e[i].flag) fff[to] = true;
      if (!dfs(to, now)) {
        return false;
      }
      if (!e[i].flag) {
        siz[now] += siz[to];
        sumx[now] += sumx[to];
      }
    }
  }
  if (fff[now]) {
    if (sum_all - sumx[now] - max(n - siz[now] - sumx[now], 0LL) <
        (long long)siz[now])
      return false;
    else
      return true;
  } else
    return true;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%d", &E[i].from, &E[i].to, &E[i].dist);
    add_edge(E[i]);
  }
  sort(E + 1, E + n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &xx[i]);
    sum_all += xx[i];
  }
  int l = 1, r = n - 1;
  while (l < r) {
    memset(fff, 0, sizeof(fff));
    fff[1] = true;
    int mid = (l + r) >> 1;
    for (int i = 1; i < n; ++i)
      e[E[i].id].flag = e[E[i].id + 1].flag = (i <= mid);
    if (dfs(1, 0))
      r = mid;
    else
      l = mid + 1;
  }
  printf("%d", E[r].dist);
  return 0;
}