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;
struct Edge {
  int a, b, c;
  bool operator<(const Edge &r) const { return c < r.c; }
};
int N, x[3000], bl[3000];
vector<pair<int, int> > edges[3000];
Edge e[3000];
pair<int, int> dfs(int n, int p) {
  if (bl[n]) return pair<int, int>(0, 0);
  pair<int, int> ret = pair<int, int>(1, x[n]);
  for (int i = int(0); i < int(edges[n].size()); i++) {
    int next = edges[n][i].first;
    if (next == p) continue;
    pair<int, int> t = dfs(next, n);
    ret.first += t.first;
    ret.second += t.second;
  }
  return ret;
}
void block(int n) {
  if (bl[n]) return;
  bl[n] = 1;
  for (int i = int(0); i < int(edges[n].size()); i++) block(edges[n][i].first);
}
int main() {
  int a, b, c;
  while (scanf("%d", &N) != EOF) {
    for (int i = int(0); i < int(N); i++) edges[i].clear(), bl[i] = 0;
    for (int i = int(1); i < int(N); i++) {
      scanf("%d %d %d", &a, &b, &c);
      a--, b--;
      e[i] = Edge{a, b, c};
      edges[a].push_back(pair<int, int>(b, c));
      edges[b].push_back(pair<int, int>(a, c));
    }
    sort(e + 1, e + N);
    for (int i = int(0); i < int(N); i++) {
      scanf("%d", x + i);
    }
    int ac = 0, ans = 0;
    for (int i = N - 1; i; i--) {
      if (bl[e[i].a] || bl[e[i].b]) continue;
      pair<int, int> t1 = dfs(e[i].a, e[i].b);
      pair<int, int> t2 = dfs(e[i].b, e[i].a);
      if (t1.first < t2.first) swap(t1, t2), swap(e[i].b, e[i].a);
      if (t1.first > t2.second + ac) {
        ac += t2.second;
        bl[e[i].b] = 1;
        for (int j = int(0); j < int(edges[e[i].b].size()); j++) {
          int next = edges[e[i].b][j].first;
          if (next == e[i].a) continue;
          block(next);
        }
      } else {
        ans = e[i].c;
        break;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}